C Program to Implement Rabin-Karp Method for Pattern Searching

«
»
This is a C Program to implement RabinKarp method. Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.
Examples:
1) Input:
txt[] = “THIS IS A TEST TEXT”
pat[] = “TEST”
Output:
Pattern found at index 10

Here is source code of the C Program to Implement Rabin-Karp Method for String Matching. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<stdio.h>
  2. #include<string.h>
  3.  
  4. // d is the number of characters in input alphabet
  5. #define d 256
  6.  
  7. /*  pat  -> pattern
  8.     txt  -> text
  9.     q    -> A prime number
  10. */
  11. void search(char *pat, char *txt, int q)
  12. {
  13.     int M = strlen(pat);
  14.     int N = strlen(txt);
  15.     int i, j;
  16.     int p = 0;  // hash value for pattern
  17.     int t = 0; // hash value for txt
  18.     int h = 1;
  19.  
  20.     // The value of h would be "pow(d, M-1)%q"
  21.     for (i = 0; i < M-1; i++)
  22.         h = (h*d)%q;
  23.  
  24.     // Calculate the hash value of pattern and first window of text
  25.     for (i = 0; i < M; i++)
  26.     {
  27.         p = (d*p + pat[i])%q;
  28.         t = (d*t + txt[i])%q;
  29.     }
  30.  
  31.     // Slide the pattern over text one by one
  32.     for (i = 0; i <= N - M; i++)
  33.     {
  34.  
  35.         // Check the hash values of current window of text and pattern
  36.         // If the hash values match then only check for characters on by one
  37.         if ( p == t )
  38.         {
  39.             /* Check for characters one by one */
  40.             for (j = 0; j < M; j++)
  41.             {
  42.                 if (txt[i+j] != pat[j])
  43.                     break;
  44.             }
  45.             if (j == M)  // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
  46.             {
  47.                 printf("Pattern found at index %d \n", i);
  48.             }
  49.         }
  50.  
  51.         // Calculate hash value for next window of text: Remove leading digit,
  52.         // add trailing digit
  53.         if ( i < N-M )
  54.         {
  55.             t = (d*(t - txt[i]*h) + txt[i+M])%q;
  56.  
  57.             // We might get negative value of t, converting it to positive
  58.             if(t < 0)
  59.               t = (t + q);
  60.         }
  61.     }
  62. }
  63.  
  64. /* Driver program to test above function */
  65. int main()
  66. {
  67.     char *txt = "Sanfoundry C Programming Examples";
  68.     char *pat = "San";
  69.     int q = 101;  // A prime number
  70.     search(pat, txt, q);
  71.     return 0;
  72. }

Output:

advertisement
$ gcc RabinCarp.c
$ ./a.out
 
Pattern found at index 0

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

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.