C++ Program to Implement Rolling Hash

«
»
This C++ Program demonstrates operations on Rolling Hash

Here is source code of the C++ Program to demonstrate Rolling Hash. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Rolling Hash
  3.  */
  4. #include <iostream>
  5. #include <string>
  6. using namespace std;
  7.  
  8. const unsigned PRIME_BASE = 257;
  9. const unsigned PRIME_MOD = 1000000007;
  10.  
  11. /*
  12.  * Hash Function
  13.  */
  14. unsigned hash(const string& s)
  15. {
  16.     long long ret = 0;
  17.     for (int i = 0; i < s.size(); i++)
  18.     {
  19.         ret = ret * PRIME_BASE + s[i];
  20.         ret %= PRIME_MOD;
  21.     }
  22.     return ret;
  23. }
  24.  
  25. /*
  26.  * Rabin-Karp (Rolling Hash Implementation)
  27.  */
  28. int rabin_karp(const string& needle, const string& haystack)
  29. {
  30.     long long hash1 = hash(needle);
  31.     long long hash2 = 0;
  32.     long long power = 1;
  33.     for (int i = 0; i < needle.size(); i++)
  34.         power = (power * PRIME_BASE) % PRIME_MOD;
  35.  
  36.     for (int i = 0; i < haystack.size(); i++)
  37.     {
  38.         hash2 = hash2*PRIME_BASE + haystack[i];
  39.         hash2 %= PRIME_MOD;
  40.  
  41.     	if (i >= needle.size())
  42.     	{
  43.             hash2 -= power * haystack[i-needle.size()] % PRIME_MOD;
  44.             if (hash2 < 0)
  45.                 hash2 += PRIME_MOD;
  46.         }
  47.     	if (i >= needle.size()-1 && hash1 == hash2)
  48.             return i - (needle.size()-1);
  49.     }
  50.  
  51.     return -1;
  52. }
  53.  
  54. /*
  55.  * Main Contains Menu
  56.  */
  57. int main()
  58. {
  59.     cout<<"---------------------------"<<endl;
  60.     cout<<"Rolling Hash Implementation"<<endl;
  61.     cout<<"---------------------------"<<endl;
  62.     string s1,s2;
  63.     cout<<"Enter Original String: ";
  64.     getline(cin,s1);
  65.     cout<<"Enter String to find: ";
  66.     cin>>s2;
  67.     if(rabin_karp(s2, s1) == -1)
  68.         cout<<"String not found"<<endl;
  69.     else
  70.         cout<<"String "<<s2<<"found at position "<<rabin_karp(s2, s1)<<endl;
  71.         return 0;
  72. }

advertisement
$ g++ rolling.cpp
$ a.out
---------------------------
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

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn