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
