Showing posts with label KMP. Show all posts
Showing posts with label KMP. Show all posts

Sunday 17 July 2016

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