Showing posts with label Rabin Karp. Show all posts
Showing posts with label Rabin Karp. Show all posts

Sunday 17 July 2016

Program 5: Rabin Karp String Matching

MTech VTU Advanced Algorithm Lab (2nd sem)

Design, develop, and write a program to solve String matching problem using Rabin Karp algorithm and determine its performance.

#include<stdio.h>
#include<string.h>
#define d 256

void search(char pat[], char txt[], int q)
{
            int M = strlen(pat);
            int N = strlen(txt);
            int i, j;
            int p = 0;
            int t = 0;
            int h = 1;

            for (i = 0; i < M-1; i++)
                        h = (h*d) % q;
            for (i = 0; i < M; i++)
            {
                        p = (d*p + pat[i]) % q;
                        t = (d*t + txt[i]) % q;
            }
            for (i = 0; i <= N - M; i++)
            {
                    if ( p == t )
                    {
                                for (j = 0; j < M; j++)
                                    {
                                                if (txt[i+j] != pat[j])
                                                            break;
                                    }
                                   if (j == M)
                                                printf("\nPattern found at index %d", i);
                        }

                        if ( i < N-M )
                        {
                                    t = (d*(t - txt[i]*h) + txt[i+M]) % q;
                                    if (t < 0)
                                                t = (t + q);
                        }
            }
}

int main()
{
            char txt[30], pat[30];
            int q = 101; // A prime number
            printf("\n Enter the text:");
            gets(txt);
            printf("\n Enter the pattern:");
            gets(pat);
            search(pat, txt, q);
            return 0;
}

Output:
 Enter the text: abacbaaababa
 Enter the pattern: aba

Pattern found at index 0
Pattern found at index 7
Pattern found at index 9