라빈-카프 알고리즘 기본형(Rabin-Karp Algorithm)

// d is the number of characters in the input alphabet  
#define d 29  

//find txt in pattern
int RCsearch(const string& pattern , const string& txt, int q = 100003)
{
	int M = pattern.size(), N = txt.size();
	int p = 0; // hash value for pattern  
	int t = 0; // hash value for txt  
	int h = 1;

	for (int i = 0; i < M - 1; i++)
		h = (h * d) % q;

	for (int i = 0; i < M; i++){
		p = (d * p + pattern[i]) % q;
		t = (d * t + txt[i]) % q;
	}

	for (int i = 0; i <= N - M; i++){
		if (p == t){
			bool success = true;
			for (int j = 0; j < M; j++){
				if (txt[i + j] != pattern[j]) {
					success = false;
					break;
				}
			}
			if (success)
				return i;
		}
		if (i == N - M)break;

		t = (d*(t - txt[i] * h) + txt[i + M]) % q;
		if (t < 0) t = (t + q);
		
	}
}

부분 문자열을 빠르게 찾기 위한 해싱 함수입니다. 문제 상황에 따라 적절히 변형을 하면 되는데,

변수 d는 등장하는 알파벳의 개수를 저장하면 됩니다. 또한 모듈러 q를 문자열의 최댓값에 따라 적절히 변형해주어야 하는데, 20만 정도의 txt길이면 10007 혹은 100003을 사용하는 것 같았습니다. q값은 작아서도, 커서도 안돼서 문제의 변수 최댓값에 따라 적절히 조절해 주어야 합니다.

적당한 모듈러 q의 값을 찾는 방법은 아래 링크를 참조하시길 바랍니다.

cs.stackexchange.com/questions/10174/how-do-we-find-the-optimal-modulus-q-in-rabin-karp-algorithm

How do we find the optimal modulus q in Rabin-Karp algorithm?