/* 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