RabinKarp

Resource:

Tushar Roy

Abdul Bari

GeeksForGeeks

E-maxx

Implementation:

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long LL;
	int naive_matchig (string text, string pattern)
	{
	int n = text.size();
	int m = pattern.size();
	int i,j;
	for( i = 0; i < n; i++){
	for( j = 0; j < m && i +j < n; j++){
	if(text[i+j] != pattern[j]){
	break; // mismatch found , break the inner loop.
	}
	}
	if(j == m){
	return i; // match found.
	}
	}
	return -1;
	}
	/// Returns the index of the first match
	/// Complexity O(n+m), this is unsafe because it doesn't check for collision
	LL Hash(const string &s, int m, LL B, LL M)
	{
	LL h = 0, power = 1;
	for(int i = m - 1; i >= 0; i--){
	h = h + (s[i] * power) % M;
	h = h % M;
	power = (power * B) % M;
	}
	return h;
	}
	int match(const string &text, const string &pattern)
	{
	int n = text.size();
	int m = pattern.size();
	if(n < m) return -1;
	if(m == 0 or n == 0) return -1;
	LL B = 347, M = 1e9 + 7;
	// calculate B^(m-1)
	LL power = 1;
	for(int i = 1; i <= m - 1; i++)
	power = (power * B) % M;
	// find the hash value of first m characters of text
	// find hash value of pattern
	LL hash_text = Hash(text, m, B, M);
	LL hash_pattern = Hash(pattern , m, B, M);
	if(hash_text == hash_pattern){ // return the index of the match
	return 0;
	// we should've checked the substring character by character
	// here as hash collision might happen.
	}
	for(int i = m; i < n; i++){
	hash_text = (hash_text - (power * text[i - m]) % M ) % M;
	hash_text = (hash_text + M) % M; // take care of M of negative value
	hash_text = (hash_text * B) % M;
	hash_text = (hash_text + text[i]) % M;
	if(hash_text == hash_pattern){
	return i - m + 1; // returns the index of the match
	// we should've checked the substring character by character
	// here as hash collision might happen.
	}
	}
	return -1;
	}
	int main()
	{
	string text, pattern;
	cin >> text >> pattern ;
	cout << match(text, pattern)<<endl;
	cout << naive_matchig(text, pattern)<<endl;
	return 0;
	}

view raw robinKarp.cpp hosted with ❤ by GitHub

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	vector<int> rabin_karp(string const& s, string const& t)
	{
	const int p = 31;
	const int m = 1e9 + 9;
	int S = s.size();
	int T = t.size();
	//dbg2(s,t);
	vector<ll> p_pow(max(S, T));
	p_pow[0] = 1;
	for (int i = 1; i < (int)p_pow.size(); i++)
	p_pow[i] = (p_pow[i - 1] * p) % m;
	vector<ll> h(T + 1, 0);
	for (int i = 0; i < T; i++)
	h[i + 1] = (h[i] + (t[i] - 'a' + 1) * p_pow[i]) % m;
	ll h_s = 0;
	for (int i = 0; i < S; i++)
	h_s = (h_s + (s[i] - 'a' + 1) * p_pow[i]) % m;
	vector<int> occurence;
	for (int i = 0; i + S - 1 < T; i++) {
	ll cur_h = (h[i + S] + m - h[i]) % m;
	if (cur_h == h_s * p_pow[i] % m)
	occurence.push_back(i);
	}
	return occurence;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	string pattern, text;
	cin >> pattern >> text;
	// dbg2(pattern, text);
	vector<int> ans = rabin_karp(pattern, text);
	for (auto x : ans)
	cout << x << " ";
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Rabin_Karp.cpp hosted with ❤ by GitHub

 

Problems:

NAJPF - Pattern Find      SOLUTION

D. Good Substrings 

D. Palindromic characteristics 

Share: