Advertisement
Riz1Ahmed

Apply KMP

Nov 8th, 2018
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.79 KB | None | 0 0
  1. /*******Statement********
  2. Given 2 strings, 1≤P,T≤10⁵,
  3.     find occurrenced time of P in T.
  4.    
  5. °Sample Input: sds sasdsdssagsdsad
  6. °Sample Output: 3
  7. Problem Link: http://bit.ly/applyKMP
  8. *************************/
  9. #include <cstdio>
  10. #include <cstring>
  11. #define sz 100010
  12. char P[sz], T[sz];
  13. int b[sz], Plen, Tlen;
  14. void FailureTable(){
  15.     int i=0, j=-1;
  16.     b[0] = -1;
  17.     while (i<Plen){
  18.         while (j>=0 && P[i]!=P[j]) j=b[j];
  19.         i++, j++, b[i]=j;
  20.     }
  21. }
  22. int KMP(){
  23.     int i=0, j=0, ans=0;
  24.     while (i<Tlen){
  25.         while (j>=0 && T[i]!=P[j]) j=b[j];
  26.         i++, j++;
  27.         if (j==Plen) ans++, j=b[j];
  28.     }
  29.     return ans;
  30. }
  31. int main(){
  32.     scanf("%s %s",P,T);
  33.     Plen=strlen(P), Tlen=strlen(T);
  34.     FailureTable();
  35.     //for (int i=0; i<Plen; i++)
  36.         //printf("%d ",b[i]); puts("");
  37.     printf("%d\n",KMP());
  38.     return 0;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement