fork download
copy 
  1.  
  2. /* Following program is a C++ implementation of Rabin Karp  
  3. Algorithm given in the CLRS book */
  4. #include <bits/stdc++.h> 
  5. using namespace std; 
  6.  
  7. // d is the number of characters in the input alphabet  
  8. #define d 256  
  9.  
  10. /* pat -> pattern  
  11.     txt -> text  
  12.     q -> A prime number  
  13. */
  14. void search(char pat[], char txt[], int q)  
  15. {  
  16.     int M = strlen(pat);  
  17.     int N = strlen(txt);  
  18.     int i, j;  
  19.     int p = 0; // hash value for pattern  
  20.     int t = 0; // hash value for txt  
  21.     int h = 1;  
  22.  
  23.     // The value of h would be "pow(d, M-1)%q"  
  24.     for (i = 0; i < M - 1; i++)  
  25.         h = (h * d) % q;  
  26.  
  27.     // Calculate the hash value of pattern and first  
  28.     // window of text  
  29.     for (i = 0; i < M; i++)  
  30.     {  
  31.         p = (d * p + pat[i]) % q;  
  32.         t = (d * t + txt[i]) % q;  
  33.     }  
  34.  
  35.     // Slide the pattern over text one by one  
  36.     for (i = 0; i <= N - M; i++)  
  37.     {  
  38.  
  39.         // Check the hash values of current window of text  
  40.         // and pattern. If the hash values match then only  
  41.         // check for characters on by one  
  42.         if ( p == t )  
  43.         {  
  44.             /* Check for characters one by one */
  45.             for (j = 0; j < M; j++)  
  46.             {  
  47.                 if (txt[i+j] != pat[j])  
  48.                     break;  
  49.             }  
  50.  
  51.             // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]  
  52.             if (j == M)  
  53.                 cout<<"Pattern found at index "<< i<<endl;  
  54.         }  
  55.  
  56.         // Calculate hash value for next window of text: Remove  
  57.         // leading digit, add trailing digit  
  58.         if ( i < N-M )  
  59.         {  
  60.             t = (d*(t - txt[i]*h) + txt[i+M])%q;  
  61.  
  62.             // We might get negative value of t, converting it  
  63.             // to positive  
  64.             if (t < 0)  
  65.             t = (t + q);  
  66.         }  
  67.     }  
  68. }  
  69.  
  70. /* Driver code */
  71. int main()  
  72. {  
  73.     char txt[] = "GEEKS FOR GEEKS";  
  74.     char pat[] = "GEEK";  
  75.     int q = 101; // A prime number  
  76.     search(pat, txt, q);  
  77.     return 0;  
  78. }  
  79.  
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Pattern found at index 0
Pattern found at index 10
https://ideone.com/cz4waP
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!