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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.