KMP - Knuth-Morris-Pratt Pattern Matching Basic

1. #include<bits/stdc++.h>  
2. using namespace std;  
3. #define ll long long int  
4. void computeLPSArray(string pattern, int m, int lps[]){  
5.     int len=0;  
6.     lps[0]=0;   //lps[0] is always 0  
7.     int i=1;  
8.     while(i<m){  
9.         if(pattern[i]==pattern[len]){  
10.             len++;  
11.             lps[i]=len;  
12.             i++;  
13.         }else{  
14.             if(len!=0)  
15.                 len=lps[len-1];  
16.             else{  
17.                 lps[i]=0;  
18.                 i++;  
19.             }  
20.         }  
21.     }  
22. }  
23. void kmpSearch(string str,string pattern){  
24.     int m=pattern.length();  
25.     int n=str.length();  
26.     int lps[m];  //longest prefix suffix array  
27.     computeLPSArray(pattern,m,lps);  
28.     int i=0; //text  
29.     int j=0; //pattern  
30.     bool found=0;  
31.     while(i<n){  
32.         if(pattern[j]==str[i]){  
33.             i++;  
34.             j++;  
35.         }  
36.         if(j==m){  
37.             cout<<"Pattern found at index "<<i-j<<endl;  
38.             j=lps[j-1];  
39.             found=1;  
40.         }else if(i<n && pattern[j]!=str[i]){  
41.             if(j!=0) j=lps[j-1];  
42.             else i=i+1;  
43.         }  
44.     }  
45.     if(!found)cout<<"Pattern Not Found"<<endl;  
46. }  
47. int main(){  
48.     //freopen("input.txt","r",stdin);  
49.     //freopen("output.txt","w",stdout);  
50.     int t;  
51.     cin>>t;  
52.     while(t--){  
53.         string str,pattern;  
54.         cin>>str>>pattern;  
55.         kmpSearch(str,pattern);  
56.     }  
57.     return 0;  
58. }