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);
		
	}
}

 

 

 

 

 

This is a hashing function for quickly finding partial strings. You can modify it appropriately depending on the problem situation.

The variable d stores the number of alphabets that appear. You also need to modify the modulus q appropriately according to the maximum value of the string. For a txt length of about 200,000, it seems that 10007 or 100003 is used. The q value should not be too small or too large; it must be adjusted appropriately based on the maximum value of the problem's variables.

For methods to find an appropriate value for the modular q, please refer to the link below.

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?