Wednesday, February 25, 2015

KMP String Matching in C++


/*
 Program to match a pattern in a given string using KMP Algorithm
 Run time of the Algo : O(n + m)
  n - Size of String
  m - Size of Pattern
 @author - yazar : yazar.y@gmail.com
*/
#include <iostream>
#include<cstring>

using namespace std;

//Variable to strore the prefix function
//If there is a mismatch between T[i] and P[j] then we will look into 
//F[j-1] to get the next potential match location
int F[200];

//Function to compute Prefix function for the given pattern
void createPrefixTable(char P[], int m){
 int i = 1;
 int j = 0;
 //If there is a mismatch in the 0th location of pattern, 
 //it is then good to look again at 0th position for a match
 F[0] = 0;
 
 //Loop to set each field of prefix table
 while(i<m){
  //If ith location in prefix table matches that of jth location
  //then set the next location to be matched in case of failure as 
  //j+1
  if(P[i] == P[j]){
   F[i] = j+1;
   i++;
   j++;
  } else if(j>0){
   //If there is a mismatch while computing the 
   //match prefix with the pattern,
   // Set the value of j to next potential point of match
   j = F[j-1];
  } else {
   F[i] = 0;
   i++;
  }
 
 }
}

//Function to match a pattern within a text
int matchPattern(char T[], int n, char P[], int m){
 //Computing prefix table for matching
 createPrefixTable(P,m);
 int i=0, j=0;
 
 //Loop to iterate throughout the text
 while(i<n){
  //If there is a match in the current character within the pattern
  if(T[i] == P[j]){
   //If the entire pattern is matched, return current location
   if(j == (m-1) ){
    return i - j;
   } else {
    //Otherwise increment i and j, so that 
    //consecutive Pattern positions will be matched
    i++;
    j++;
   }
  } else if(j > 0){
   //If there is a mismatch, set the value 
   //of j to next potential point of Match
   //(ie. F[j-1] as there is a match till P[j-1])
   j = F[j-1];
  } else {
   i++;
  }
 }
 
 return -1;
} 

int main(){
 char P[200], T[500];
 
 //Readin the Text and pattern from user
 cout<<"Enter a pattern : ";
 cin>>P;
 
 cout<<"Enter a String : ";
 cin>>T;
 int n, m;
 
 n = strlen(T);
 m = strlen(P);
 
 //Calling the function to perform match
 int location = matchPattern(T,n,P,m);
 
 if(location == -1){
  cout<<"Pattern "<<P<<" Not found in String "<<T<<"\n";
 } else {
  cout<<"Pattern "<<P<<" found in the string "<<T<<" at "<<location<<"\n";
 }
 return(0);
}

No comments:

Post a Comment