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