글 읽기 - 라빈 카프로 풀 수 있는건가요?

hanil0623 3년 전 0

라빈 카프로 문제를 풀고 싶습니다. power를 2씩 곱하고 모듈러 연산을 사용하지 않으니 틀렸다고 나오고

해시 충돌이 나서 그런가 싶어 모듈러와 power 값을 막 바꿔봐도 틀렸다고 나옵니다.

어떻게 해결할 수 있을까요? 아니면 제 코드가 잘못 된것일까요?

#include<iostream>
#define MAX 1000009
#define MOD 100000007
using namespace std;
char text[MAX]; char pat[MAX];
int n, m;

inline int mod(long long n) {
	if (n >= 0) return n % MOD;
	return ((-n / MOD + 1) * MOD + n) % MOD;
}

int solution() {
	int psize = 2 * n + 1;
	long long pHash = 0, tHash = 0, power = 1;
	int ans = 0;
	for (int i = 0; i <= m - psize; i++) {
		if (i == 0) {
			for (int j = 0; j < psize; j++) {
				pHash = mod(pHash + pat[psize - 1 - j] * power);
				tHash = mod(tHash + text[psize - 1 - j] * power);
				if (j < psize - 1) {
					power = mod(power * 2);
				}
			}
		}
		else {
			tHash = mod(2 * (tHash - text[i - 1] * power) + text[psize - 1 + i]);
		}
		if (pHash == tHash) {
			// 해시 값이 같을 경우 답이라고 판정
			// O(nm)을 방지하기 위함
			ans++;
		}
	}
	return ans;
}

int main() {
	cin >> n >> m;
	cin >> text;

	for (int i = 0; i < 2 * n + 1; i++) {
		if (i % 2 == 0) pat[i] = 'I';
		else pat[i] = 'O';
	}
	cout << solution();
	return 0;
}