KMP Knuth Morris Pratt Matcher algorithm

//KMP (Knuth-Morris-Pratt) Matcher algorithm implementation.
#include<stdio.h>
#include<iostream.h>
#include<conio.h>
#include<string.h>

char p[100],t[100];
int m,n,pie[100];

void compute_prefix_function()
{
 pie[1]=0;
 int k=0;
 for(int q=2;q<=m;q++)
 {
  while((k>0) && (p[k+1]!=p[q]))
   k=pie[k];
  if((p[k+1])==p[q])
   k=k+1;
  pie[q]=k;
 }
}

void kmp_matcher()
{
 compute_prefix_function();
 int q=0;
 printf("Pattern occurs at: ");
 for(int i=1;i<=n;i++)
 {
  while((q>0) && (p[q+1]!=t[i]))
   q=pie[q];

  if((p[q+1])==t[i])
   q=q+1;

  if(q==m)
  {
   cout<<i-m<<" ";
   q=pie[q];
  }
 }
}

void main()
{
 clrscr();
 cout<<"enter the length of String: ";
 cin>>n;
 cout<<"Enter the string: ";
 for(int i=1;i<=n;i++)
  cin>>t[i];

 cout<<"enter the length of pattern: ";
 cin>>m;
 cout<<"Enter the Pattern: ";
 for(i=1;i<=m;i++)
  cin>>p[i];
 kmp_matcher();
 getch();
}
//program written by Mars.

Related Posts by Categories