16916部分文字列

質問する
文字列s,pを与えると,pがsであるかどうかの部分文字列を探し出す!
の意見を打診
Pythonのp insが書いてあるかどうかを見つけてみました.
長さが100万なのでこれは無理そうです
いろいろな方法で探してもだめだと言った!ううう
しかし,これらの部分文字列のO(n)を検索する時間的複雑さという2つの有名なアルゴリズムがある.
KMPとラビンカフアルゴリズムのようですが、
KMPは複雑なので、ラビン・カフアルゴリズムで解きたいです.
ラビン・カフアルゴリズム
pとsの部分文字列のハッシュ値が得られ、ハッシュ値が同じである場合.
これは、本当に同じ文字列であるかどうかを確認する方法です.
sをpの長さに切って、ハッシュ値を出します.
実際,比較のたびにハッシュコードを取得し比較する動作の時間的複雑さはO(s*p)である.
O(n)になるにはどうすればいいの~?
スライドウィンドウから縮こまって見る
一番左のハッシュ値を抜き、一番右のハッシュ値を加えて対称に~~
2つのポインタの感覚でプッシュした後、O(n)だけで比較できます!
実施方法は以下の通りである
ハッシュ関数
各文字のアスキー値に2^baseを乗算し、文字の和をハッシュコードとして使用します!
値が大きすぎる可能性がありますのでmod演算を行ってください
スライドウィンドウでナビゲート
一番左の文字列のハッシュ値を削除し、
桁数を調整する.
一番右のアルファベットのハッシュ値を加えればいいです.
桁数を調整する部分にあります.
なぜhash s=(hash s+mod)%mod;君がそんなことをするとは知らなかった.
hash sは一番左のhash値を引いて、負数になりましたか?
mod値を加えて、modに分けます!
c++では、-1%4は-1なので、3
(-1+4)%4は一緒にやるからこんなんだよ~~
Pythonは-1%4が3!
しかし、私はあなたが初めて私を助けてくれたことをよく理解していません.
ただ次回は文字列の一部を求める必要がある場合があります.
あ~O(n)はなんとかなります~~じゃあ、ラビン・カフさんだと思って~~このように出して使いましょう!

この問題の例
s,pが与えられたとき,sが入れ替わる文字列はpですか.
s : abc
p : bca
sに2倍、そこでpは部分文字列の問題です!うわーう
abcabcはbcaが部分文字列であることを示しますか?

コード#コード#

#include <iostream>
#include <string>

using namespace std;

int mod = 127;
int base = 256;

//해시값 구하는 함수
//각 문자의 아스키코드에 2^base를 곱해주고
//그 합을 해시값으로 지정
int h(string s) {
	int ans = 0;
	for (auto ch : s) {
		ans = (ans * base + ch) % mod;
	}
	return ans;
}

int main() {
	string s, p;
	cin >> s >> p;

	int sl = s.size();
	int pl = p.size();

	if (sl < pl)
	{
		cout << "0\n";
		return 0;
	}

	int hash_s = h(s.substr(0, pl));
	int hash_p = h(p);
	
	int first = 1;
	for (int i = 0; i < pl - 1; i++) {
		first = (first * base) % mod;
	}

	for (int i = 0; i <= sl - pl; i++)
	{
		if (hash_p == hash_s)
		{
			if (s.substr(i, pl) == p) {
				cout << "1";
				return 0;
			}
		}
		if ((i + pl) < sl)
		{
			hash_s = hash_s - (s[i] * first) % mod; //맨 왼쪽 글자 해시 값 빼주고
			hash_s = (hash_s + mod) % mod; //자릿수 맞춰주고
			hash_s = ((hash_s * base) % mod + s[i + pl]) % mod; //맨 오른쪽 글자 추가해줘
		}

	}
	cout << "0";
}