﻿ Tips And Tutorial - Presented by Oneous!

Knuth - Morris - Pratt algorithm (KMP String Matching Algorithm)
Last Update: 6 June, 2010

Problem: Given a string ‘S’, the problem of string matching deals with finding whether a pattern ‘p’ occurs in ‘S’ and if ‘p’ does occur then returning position in ‘S’ where ‘p’ occurs.

My Code:

``````// C++ code of KMP String Matching Algorith
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>

using namespace std;

void FailureFunction(char P[], int F[],int m){
int i,j;
F[0]=0;	//  assignment is important
j=0;
i=1;
while(i<m){ // that i is less than the length of patter
if(P[i]==P[j]){
F[i]=j+1;
i++;
j++;
}else if(j>0){
j=F[j-1];
}else {
F[i]=0;
i++;
}
}
}

int KMP(char T[], char P[]){
int i,j,F[100];	// the maximum size of Pattern Strin
int m=strlen(P);
int n=strlen(T);
FailureFunction(P,F,m);
i=0;
j=0;
while(i<n){
if(T[i]==P[j]){
if(j==m-1)
return i-j; // means, in (i-j)th position, there is a match occu
else{
i++;
j++;
}
}else if(j>0){
j=F[j-1];
}else{
i++;
}
}
return -1; // No match foun
}

int main()
{
//freopen("in.txt","rt",stdin)
//freopen("out.txt","wt",stdout)

char T[1000],P[100];

while(gets(T)){
gets(P);
int pos=KMP(T,P);
if(pos!=-1)
cout<<"String Occur at position: "<<pos<<endl;
else
cout<<"No match found"<<endl;

}

// End of main function.......
return 0;
}

/***  Programmed by:
###########################
##   ORONNO   #############