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. }  
by - No comments:
Labels:

[ LightOJ ] 1255- Substring Frequency 

Author            : Anwar Jahid Ruman Hossain 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : [ LightOJ ] 1255- Substring Frequency
Source            : URI Online Judge
Category          : Pattern Searching
Algorithm         : Z-algorithm
Verdict           : Accepted

  1. /*__//\\//\\//\\//\\//\\= BISMILLAHIR RAHMANIR RAHIM =//\\//\\//\\//\\//\\//__*/  
  2. #include <bits/stdc++.h>  
  3. //........................</HEADER>................................  
  4. #include <ext/pb_ds/assoc_container.hpp> // Common file  
  5. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update  
  6. #include <ext/pb_ds/detail/standard_policies.hpp>  
  7.   
  8. using namespace std;  
  9. //........................</CONSTANT DEFINE>........................  
  10. const unsigned int MOD = 1000000007;  
  11. #define ll long long  
  12.   
  13. #define Imax 1e9+5  
  14. #define LLmax 1e18  
  15.   
  16. #define Imin -1e9-5  
  17. #define LLmin -1e18  
  18.   
  19. #define PI acos(-1.0)  
  20. #define EPS 1e-9  
  21. #define INF 1<<28  
  22.   
  23. //........................</LOOP >.................................  
  24. #define rep(i,a,n) for(int i=a;i<n;i++)  
  25. #define per(i,a,n) for(int i=n-1;i>=a;i--)  
  26.   
  27. //................</ STANDARTD TEMPLATE LIBRARY>...................  
  28. #define all(x) (x).begin(),(x).end()  
  29. #define pb(x) push_back(x)  
  30. #define mp(a,b) make_pair((a),(b))  
  31.   
  32. //........................</ TYPE CONVERSION>......................  
  33. #define toRad(a) ((a)*(PI)/180)  
  34. #define toDeg(a) ((a)*180/(PI))  
  35.   
  36. //........................</ MATH>.................................  
  37. #define max3(a,b,c) max(a,max(b,c))  
  38. #define min3(a,b,c) min(a,min(b,c))  
  39. #define sq(a) ((a)*(a))  
  40. inline bool isEq(double a,double b){  
  41.     return (abs(a-b)<EPS);  
  42. }  
  43. template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}  
  44. template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}  
  45.   
  46. //........................</ ARRAY DEFAULT>........................  
  47. #define mem(a,v) memset(a,v,sizeof(a))  
  48. string day [] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};  
  49. int month[]={31,28,31,30,31,30,31,31,30,31,30,31};  //Not Leap Year  
  50.   
  51. //........................</DIRECTION>.............................  
  52. int dx4[]={1,0,-1,0};  
  53. int dy4[]={0,1,0,-1}; //4 Direction  
  54.   
  55. int dx8[]={1,1,0,-1,-1,-1,0,1};  
  56. int dy8[]={0,1,1,1,0,-1,-1,-1};//8 direction  
  57.   
  58. int dxh[]={2,1,-1,-2,-2,-1,1,2};  
  59. int dyh[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction (horse)  
  60.   
  61. //........................</ INPUT/OUTPUT>.........................  
  62. #define read(n) scanf("%d",&n)  
  63. #define write(n) printf("%d",n)  
  64. #define endl '\n'  
  65.   
  66. #define PRECISION(x) cout << fixed << setprecision(x)  
  67. #define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);  
  68.   
  69. //.......................</ PRE DEFINED FUNCTIONS>..................  
  70. bool sortByFirst(const pair<int,int>&a,const pair<int,int>&b){  
  71.     return a.first>b.first;  
  72. }  
  73. //vector <string> v;  
  74. //void dfs (string str, string t = "", int cnt = 0) {  
  75. //    if (cnt == 2) {  
  76. //        v.push_back (t);  
  77. //        return;  
  78. //    } else {  
  79. //        for (int i = 0; i <(int)str.size (); i ++) {  
  80. //            dfs (str, t + str [i], cnt + 1);  
  81. //        }  
  82. //    }  
  83. //}  
  84. //vector<vector<int> >divisor(100005);  
  85. //void divisors(){  
  86. //    for(int i=1;i<100005;i++){  
  87. //        for(int j=i;j<100005;j+=i){  
  88. //           divisor[j].push_back(i);  
  89. //        }  
  90. //    }  
  91. //}  
  92. void getZarray(string str, int z[]){  
  93.     int n=str.length();  
  94.     int left,right,k;  
  95.     left=right=0;  
  96.     for(int i=1;i<n;i++){  
  97.         if(i>right){  
  98.             left=right=i;  
  99.             while(right<n && str[right-left]==str[right]){  
  100.                 right++;  
  101.             }  
  102.             z[i]=right-left;  
  103.             right--;  
  104.         }else{  
  105.             k=i-left;  
  106.             if(z[k]<right-i+1){  
  107.                 z[i]=z[k];  
  108.             }else{  
  109.                 left=i;  
  110.                 while(right<n && str[right-left]==str[right]){  
  111.                     right++;  
  112.                 }  
  113.                 z[i]=right-left;  
  114.                 right--;  
  115.             }  
  116.         }  
  117.     }  
  118. }  
  119. int period_count(string text,string pattern){  
  120.     string concat=pattern+"$"+text;  
  121.     int cnt=0;  
  122.     int len=concat.length();  
  123.     int z[len];  
  124.     getZarray(concat,z);  
  125.     int flag=0;  
  126.     for(int i=1;i<len;i++){  
  127.         if(z[i]==pattern.length()){  
  128.             cnt++;  
  129.         }  
  130.     }  
  131.     return cnt;  
  132. }  
  133. int main () {  
  134.     FAST_IO  
  135. //    freopen("input.txt","r",stdin);  
  136. //    freopen("output.txt","w",stdout);  
  137.   
  138.     int t;  
  139.     cin>>t;  
  140.     for(int i=1;i<=t;i++){  
  141.         string text,pattern;  
  142.         cin>>text>>pattern;  
  143.         cout<<"Case "<<i<<": "<<period_count(text,pattern)<<endl;  
  144.     }  
  145.     return 0;  
  146. }  
by - No comments:
Labels:
Subscribe to: Posts (Atom)