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

Program 4: Finite Automata string matching

MTech VTU Advanced Algorithm Lab (2nd sem)

Design, develop, and write a program to solve String matching problem using Finite Automata and determine its performance.

#include<stdio.h>

#include<string.h>

#define CHARS 256

int getNextState(char pat[30], int M, int state, int x)

{

            int ns, i;

            if (state < M && x == pat[state])

                        return state+1;

            for (ns = state; ns > 0; ns--)

            {

                        if(pat[ns-1] == x)

                        {

                                    for(i = 0; i < ns-1; i++)

                                    {

                                                if (pat[i] != pat[state-ns+1+i])

                                                break;

                                    }

                                    if (i == ns-1)

                                                return ns;

                        }

            }

            return 0;

}

void computeTF(char pat[30], int M, int TF[][CHARS])

{

            int state, x;

            for (state = 0; state <= M; ++state)

                        for (x = 0; x < CHARS; ++x)

                                    TF[state][x] = getNextState(pat, M,  state, x);

}

void search(char pat[30], char txt[30])

{

            int M = strlen(pat);

            int N = strlen(txt);

            int TF[M+1][CHARS];

            int i, state=0;

            computeTF(pat, M, TF);

           for (i = 0; i < N; i++)

            {

                        state = TF[state][txt[i]];

                        if (state == M)

                        {

                                    printf ("\nPattern found at index %d", i-M+1);

                        }

            }

}

int main()

{

            char txt[30], pat[30];

            printf("\nEnter the text:");

            gets(txt);

            printf("\nEnter the pattern:");

            gets(pat);

            search(pat, txt);

            return 0;

}

Output:

Case 1:

Enter the text: ababacabaabcaba

Enter the pattern: aba

Pattern found at index 0

Pattern found at index 2

Pattern found at index 6

Pattern found at index 12

Case 2:

Enter the text: abababacaba

Enter the pattern: ababaca

Pattern found at index 2

Program 3: Naive and KMP

MTech VTU Advanced Algorithm Lab (2nd sem)

Design, develop, and write a program to solve string matching problem using naïve approach and the KMP algorithm. Compare their performances.

#include<stdio.h>

#include<string.h>

int NaiveString(char t[30],char p[30], int n, int m);

int KMP(char t[30],char p[30], int n, int m);

int main()

{

            int n, m;

            char p[15], t[50];

            printf("\n Enter the text:");

            gets(t);

            printf("\n Enter the pattern:");

            gets(p);

            n = strlen(t);

            m = strlen(p);

           

           printf("\nNaive String Algorithm: ");

            NaiveString(t, p, n, m);

            printf("\n\n\nKMP String Algorithm: ");

            KMP(t, p, n, m);

}

int NaiveString(char t[30], char p[30], int n, int m)

{

            int i, j, found=0;

            for(i = 0; i < =n-m; i++)

            {

                        for(j = 0; j < m; j++)

                         {

                                    if(t[i+j] != p[j])

                                                break;

                        }

                        if(j == m)

                        {

                                 printf("\n   The pattern found at position:%d", i+1);

                                 found = 1;

                        }

             }

              if(found == 0)

                        printf("\n   Pattern not found");

}

int KMP(char t[30], char p[30], int n, int m)

{

            int pi[25];

            int i, k, flag = 1;

            pi[0] = 0, k = 0;

            for(i = 1; i < m; i++)

            {

                        while((k>0) && (p[k] != p[i]))

                                    k = pi[k-1];

                        if(p[k] == p[i])

                                    k++;

                        pi[i] = k;

            }

            printf("\nPI[] array is as follows:\n");

            for(i = 0; i < m; printf("\nPI[%d] = %d", i, pi[i]), i++);

            k = 0;

            for(i = 0; i < n; i++)

            {

                        while(k>0 && (p[k] != t[i]))

                                    k = pi[k-1];

                        if(p[k] == t[i])

                                    k++;

                        if(k == m)

                        {

                                    flag = 0;

                                    printf("\n  Pattern match occurs at position %d:", i-m+2);

                                    k = pi[k-1];

                         }

            }

            if(flag == 1)

                        printf("\n Pattern not found!!!\n\n");

            return 0;

}

Output:

Case 1:

Enter the text: bacbabababacaca

Enter the pattern: ababaca

Naive String Algorithm:

   The pattern found at position: 7

KMP String Algorithm:

PI[] array is as follows:

PI[0] = 0

PI[1] = 0

PI[2] = 1

PI[3] = 2

PI[4] = 3

PI[5] = 0

PI[6] = 1

    Pattern match occurs at position: 7

Case 2:

Enter the text: aabaacaadaabaaabaa

Enter the pattern: aaba

Naive String Algorithm:

   The pattern found at position:1

   The pattern found at position:10

   The pattern found at position:14

KMP String Algorithm:

PI[] array is as follows:

PI[0] = 0

PI[1] = 1

PI[2] = 0

PI[3] = 1

  Pattern match occurs at position: 1

  Pattern match occurs at position: 10

  Pattern match occurs at position: 14

Program 2: Monte Carlo Algorithm

MTech VTU Advanced Algorithm Lab (2nd sem)

Design, develop, and write a program to implement a Monte Carlo algorithm to test the primality of a given integer and determine its performance.

#include<stdio.h>

#include<stdlib.h>

int Modular_Exponentiation(int, int, int);

void Binary(int, int *, int *);

int main()

{

            int n, res;

            printf("\n Enter a no n:");

            scanf("%d", &n);

            if(n <= 0)

            {

                        printf("\n Please enter a +ve number!!!");

                        exit(0);

            }

            res = Modular_Exponentiation(2,n-1,n);

            if(n == 1)

                        printf("\n %d is prime!!!", n);

            else if((res % n) == 1)

                        printf("\n %d is prime!!!", n);

            else

                        printf("\n %d is not prime!!!", n);

            return 0;

}

int Modular_Exponentiation(int a, int b, int n)

{

            int c, d, bin[20] = {0}, k, i;

            c=0, d=1;

            Binary(b, bin, &k);

            for(i = k; i >= 0; i--)

            {

                        c = 2*c;

                        d = (d*d) % n;

                        if(bin[i] == 1)

                        {

                                    c++;

                                    d = (d*a) % n;

                        }

                        printf("\n i=%d, bi=%d, c=%d, d=%d", i, bin[i], c, d);

            }

            return d;

}

void Binary(int b, int *bin, int *k)

{

            int i = 0, n = b;

            *k = 0;

            *bin = 0;

            while(b != 0)

            {

                        bin[i] = b % 2;

                        *k = *k+1;

                        b /= 2;

                        i++;

            }

            *k = *k-1;

            printf("\n Binary equivalent of %d is:", n);

            for(i = *k; i >= 0; printf("%5d", bin[i--]) );

}

Output:

Case 1:

 Enter a no n: 5 

 Binary equivalent of 4 is:    1    0    0

 i=2, bi=1, c=1, d=2

 i=1, bi=0, c=2, d=4

 i=0, bi=0, c=4, d=1

 5 is prime!!!

Case 2:

 Enter a no n:9

 Binary equivalent of 8 is:    1    0    0    0

 i=3, bi=1, c=1, d=2

 i=2, bi=0, c=2, d=4

 i=1, bi=0, c=4, d=7

 i=0, bi=0, c=8, d=4

 9 is not prime!!!