This is a menu driven program on pattern Matching. structure is used here for the pattern matching.
#include
#include
struct tag
{
char pattern[100];
char text[20];
};
void improved(struct tag obj)
{
char *pat=obj.pattern;
char *txt=obj.text;
int len1 = strlen(pat);
int len2 = strlen(txt);
int i = 0,j;
printf("The text is found in the pattern at the following indices : ");
while (i {
for (j = 0; j if (pat[i + j] != txt[j])
break;
if (j == len2)
{
printf(" %d ",i);
i = i + len2;
}
else if (j == 0)
i = i + 1;
else
i = i + j;
}
}
void naive(struct tag obj)
{
int array[20];
int index=-1;
char *mainString=obj.pattern;
char *text=obj.text;
int patLen = strlen(text);
int strLen = strlen(mainString);
int i,j;
for(i = 0; i {
for(j = 0; j {
if(mainString[i+j] != text[j])
break;
}
if(j == patLen)
{ //the text is found
array[++index] = i;
}
}
printf("The text is found in the pattern at the following indices : ");
for(i=0;i printf(" %d",array[i]);
}
void arrange(char* pat, int M, int* pps)
{
int length = 0;
pps[0] = 0;
int i = 1;
while (i {
if (pat[i] == pat[length])
{
length++;
pps[i] = length;
i++;
}
else
{
if (length != 0)
length = pps[length - 1];
else
{
pps[i] = 0;
i++;
}
}
}
}
void KMP(struct tag obj)
{
char* pattern=obj.pattern;
char* text=obj.text;
int M = strlen(text);
int N = strlen(pattern);
int pps[M];
arrange(obj.text, M, pps);
int i = 0;
int j = 0;
printf("The text is found in the pattern at the following indices : ");
while (i {
if (obj.text[j] == obj.pattern[i])
{
j++;
i++;
}
if (j == M)
{
printf(" %d", i - j);
j = pps[j - 1];
}
else if (i {
if (j != 0)
j = pps[j - 1];
else
i = i + 1;
}
}
}
void main()
{
struct tag obj;
int ch,f;
printf("\nEnter the pattern string (LIKE 'This is a test'): ");
gets(obj.pattern);
printf("\nEnter the text string (LIKE 'is'): ");
gets(obj.text);
while(1)
{
printf("\nEnter 1 for Naive pattern matching, 2 for improved Naive pattern matching and 3 KMP algorithm: ");
scanf("%d",&ch);
f=0;
switch(ch)
{
case 1:
naive(obj);
break;
case 2:
improved(obj);
break;
case 3:
KMP(obj);
break;
default:
f=1;
}
if(f==0)
break;
}
getch();
}
#include
struct tag
{
char pattern[100];
char text[20];
};
void improved(struct tag obj)
{
char *pat=obj.pattern;
char *txt=obj.text;
int len1 = strlen(pat);
int len2 = strlen(txt);
int i = 0,j;
printf("The text is found in the pattern at the following indices : ");
while (i {
for (j = 0; j if (pat[i + j] != txt[j])
break;
if (j == len2)
{
printf(" %d ",i);
i = i + len2;
}
else if (j == 0)
i = i + 1;
else
i = i + j;
}
}
void naive(struct tag obj)
{
int array[20];
int index=-1;
char *mainString=obj.pattern;
char *text=obj.text;
int patLen = strlen(text);
int strLen = strlen(mainString);
int i,j;
for(i = 0; i {
for(j = 0; j
if(mainString[i+j] != text[j])
break;
}
if(j == patLen)
{ //the text is found
array[++index] = i;
}
}
printf("The text is found in the pattern at the following indices : ");
for(i=0;i printf(" %d",array[i]);
}
void arrange(char* pat, int M, int* pps)
{
int length = 0;
pps[0] = 0;
int i = 1;
while (i {
if (pat[i] == pat[length])
{
length++;
pps[i] = length;
i++;
}
else
{
if (length != 0)
length = pps[length - 1];
else
{
pps[i] = 0;
i++;
}
}
}
}
void KMP(struct tag obj)
{
char* pattern=obj.pattern;
char* text=obj.text;
int M = strlen(text);
int N = strlen(pattern);
int pps[M];
arrange(obj.text, M, pps);
int i = 0;
int j = 0;
printf("The text is found in the pattern at the following indices : ");
while (i {
if (obj.text[j] == obj.pattern[i])
{
j++;
i++;
}
if (j == M)
{
printf(" %d", i - j);
j = pps[j - 1];
}
else if (i {
if (j != 0)
j = pps[j - 1];
else
i = i + 1;
}
}
}
void main()
{
struct tag obj;
int ch,f;
printf("\nEnter the pattern string (LIKE 'This is a test'): ");
gets(obj.pattern);
printf("\nEnter the text string (LIKE 'is'): ");
gets(obj.text);
while(1)
{
printf("\nEnter 1 for Naive pattern matching, 2 for improved Naive pattern matching and 3 KMP algorithm: ");
scanf("%d",&ch);
f=0;
switch(ch)
{
case 1:
naive(obj);
break;
case 2:
improved(obj);
break;
case 3:
KMP(obj);
break;
default:
f=1;
}
if(f==0)
break;
}
getch();
}
This post first appeared on Tutorial Site On Computer Programming Languages F, please read the originial post: here
