Code:
#include iostream
#include string
using namespace std;
const unsigned PRIME_BASE = 257;
const unsigned PRIME_MOD = 1000000007;
/*
* Hash Function
*/
unsigned hash(const string& s)
{
long long ret = 0;
for (int i = 0; i < s.size(); i++)
{
ret = ret * PRIME_BASE + s[i];
ret %= PRIME_MOD;
}
return ret;
}
/*
* Rabin-Karp (Rolling Hash Implementation)
*/
int rabin_karp(const string& needle, const string& haystack)
{
long long hash1 = hash(needle);
long long hash2 = 0;
long long power = 1;
for (int i = 0; i < needle.size(); i++)
power = (power * PRIME_BASE) % PRIME_MOD;
for (int i = 0; i < haystack.size(); i++)
{
hash2 = hash2*PRIME_BASE + haystack[i];
hash2 %= PRIME_MOD;
if (i >= needle.size())
{
hash2 -= power * haystack[i-needle.size()] % PRIME_MOD;
if (hash2 < 0)
hash2 += PRIME_MOD;
}
if (i >= needle.size()-1 && hash1 == hash2)
return i - (needle.size()-1);
}
return -1;
}
/*
* Main Contains Menu
*/
int main()
{
cout<<"---------------------------"<
cout<<"Rolling Hash Implementation"<
cout<<"---------------------------"<
string s1,s2;
cout<<"Enter Original String: ";
getline(cin,s1);
cout<<"Enter String to find: ";
cin>>s2;
if(rabin_karp(s2, s1) == -1)
cout<<"String not found"<
else
cout<<"String "<
return 0;
}
Output:
---------------------------
Rolling Hash Implementation
---------------------------
Enter Original String: sanfoundry
Enter String to find: o
String ofound at position 4
------------------
(program exited with code: 0)
Press return to continue
More C++ Programs:
