MTech Advanced Algorithm Lab (14SCS26)

Programs:

1. Design, develop, and write a program to implement the Bellman-Ford algorithm and determine its performance. Give its applications.
2. Design, develop, and write a program to implement a Monte Carlo algorithm to test the primality of a given integer and determine its performance.
3. Design, develop, and write a program to solve string matching problem using naïve approach and the KMP algorithm. Compare their performances.
4. Design, develop, and write a program to solve String matching problem using Finite Automata and determine its performance.
5. Design, develop, and write a program to solve String matching problem using Rabin Karp algoritm and determine its performance.

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