Scribd
Upload
10 views3 pages

Pattern Matching Algorithms in C

The document contains two programs that implement pattern matching algorithms: Knuth-Morris-Pratt and Boyer-Moore. Each program includes the necessary code to search for a specific pattern within a given text string. Both algorithms are demonstrated with the same example text and pattern, providing output indicating whether the pattern is present and its position in the text.

Uploaded by

À Praneeth Reddy
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
10 views3 pages

Pattern Matching Algorithms in C

The document contains two programs that implement pattern matching algorithms: Knuth-Morris-Pratt and Boyer-Moore. Each program includes the necessary code to search for a specific pattern within a given text string. Both algorithms are demonstrated with the same example text and pattern, providing output indicating whether the pattern is present and its position in the text.

Uploaded by

À Praneeth Reddy
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

DATA STRUCTURES LAB

WEEK-12 EXPERIMENTS

1. Write a program to Implement a Pattern matching algorithms using Knuth-


Morris-Pratt

#include <stdio.h>
#include <string.h>
int lps[100];
void longestPrefixSuffix(char p[])
{
int i=1,j=0;
int m = strlen(p);
lps[0] = 0;
while(i < m)
{
if( p[j] == p[i])
{
lps[i]=j+1;
i++;
j++;
}
else if(j>0)
j = lps[j-1];
else
{
lps[i]=0;
i++;
}
}
}

int kmp (char p[],char t[])


{
int n,m;
int i=0,j=0;
n = strlen(t);
m = strlen(p);
longestPrefixSuffix(p);
while( i < n )
{
if ( p[j] == t[i])
{
if (j == m-1 )
return i-j;
i++;
j++;
}
else if(j>0)
j = lps[j-1];
else
i++;
}
return 0;
}

int main() {
char t[]="kiss*miss*in*mississippi";
char p[]="missi";
int i;
i=kmp(p,t);
if(i)
printf("pattern is present in text at position %d",i+1);
else
printf("pattern is not present in text");
return 0;
}

2. Write a program to Implement a Pattern matching algorithms using Boyer-


Moore
#include <stdio.h>
#include <string.h>

int max(int a, int b)


{
if(a > b)
return a;
else
return b;
}
int boyermorre(char p[],char t[])
{
int bctable[128],i,j,k;
int n = strlen(t);
int m = strlen(p);
for(j=0; j<128; j++)
{
bctable[j]=m;
}
for(j=0; j<m; j++)
{
k=(int)p[j];
bctable[k]=m-j-1;
}
i=m-1;
while(i < n)
{
j=m-1;
while(j >= 0 && p[j] == t[i])
{
i--;
j--;
}
if(j == -1)
return i+1;
i = i + max((int)bctable[t[i]],m-j);
}
return 0;
}

int main() {
char t[]="kiss*miss*in*mississippi";
char p[]="missi";
int i;
i=boyermorre(p,t);
if(i)
printf("pattern is present in text at position %d",i+1);
else
printf("pattern is not present in text");
return 0;
}

You might also like