Rabin-Karp Algorithm in C++

This C++ Program demonstrates the implementation of Rabin-Karp Algorithm.

Here is source code of the C++ Program to demonstrate the implementation of Rabin-Karp Algorithm. 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 Rabin-Karp Algorithm
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <cstdlib>
  8. using namespace std;
  9. #define d 256
  10. /*
  11.  * search a substring in a string 
  12.  */
  13. void search(char *pat, char *txt, int q)
  14. {
  15.     int M = strlen(pat);
  16.     int N = strlen(txt);
  17.     int i, j;
  18.     int p = 0;
  19.     int t = 0;
  20.     int h = 1;
  21.     for (i = 0; i < M - 1; i++)
  22.         h = (h * d) % q;
  23.     for (i = 0; i < M; i++)
  24.     {
  25.         p = (d *p + pat[i]) % q;
  26.         t = (d * t + txt[i]) % q;
  27.     }
  28.     for (i = 0; i <= N - M; i++)
  29.     {
  30.         if (p == t)
  31.         {
  32.             for (j = 0; j < M; j++)
  33.             {
  34.                 if (txt[i + j] != pat[j])
  35.                     break;
  36.             }
  37.             if (j == M)
  38.             {
  39.                 cout<<"Pattern found at index: "<<i<<endl;
  40.             }
  41.         }
  42.         if (i < N - M)
  43.         {
  44.             t = (d * (t - txt[i] * h) + txt[i + M]) % q;
  45.             if (t < 0)
  46.               t = (t + q);
  47.         }
  48.     }
  49. }
  50.  
  51. /* Main */
  52. int main()
  53. {
  54.     char *txt = "Sanfoundry Linux Training";
  55.     char *pat = "nux";
  56.     int q = 101;
  57.     search(pat, txt, q);
  58.     return 0;
  59. }

$ g++ rabinkarp.cpp
$ a.out
 
Pattern found at index: 13
 
------------------
(program exited with code: 1)
Press return to continue

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

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 & discussions at Telegram SanfoundryClasses.