SHARE
TWEET

Untitled

a guest Aug 13th, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. int failure[3003];
  7. int cnt;
  8. void build_failure_function(string pattern, int m) {
  9.   failure[0] = 0;
  10.   failure[1] = 0; //base case
  11.  
  12.   for(int i = 2; i <= m; i++) {  //i is length of the prefix we are dealing with
  13.     // j is the index of the largest next partial match
  14.     // (the largest suffix/prefix) of the string under index i - 1
  15.     int j = failure[i - 1];
  16.     while(true) {
  17.       // check if the last character of prefix of length i "expands" the current "candidate"
  18.       if(pattern[j] == pattern[i - 1]) {
  19.         failure[i] = j + 1;
  20.         break;
  21.       }
  22.       // if we cannot "expand" even the empty string
  23.       if(j == 0) {
  24.           failure[i] = 0;
  25.           break;
  26.       }
  27.       // else go to the next best "candidate" partial match
  28.       j = failure[j];
  29.     }
  30.   }
  31. }
  32.  
  33.  
  34. bool kmp(string text, string pattern)
  35. {
  36.   int n = text.size();
  37.   int m = pattern.size();
  38.   build_failure_function(pattern, m);
  39.  
  40.   int i = 0; // the initial state of the automaton is
  41.          // the empty string
  42.  
  43.   int j = 0; // the first character of the text
  44.  
  45.   while(true) {
  46.     if(j == n) {
  47.         return false; //reached the end of the text
  48.     }
  49.  
  50.     // character matched
  51.     if(text[j] == pattern[i]) {
  52.       i++; // change the state of the automaton
  53.       j++; // get the next character from the text
  54.       if(i == m) {
  55.           cnt++;
  56.       }
  57.     } else {
  58.         if (i == 0) {
  59.             // if we reached the empty string and failed to
  60.             // "expand" even it; we go to the next
  61.             // character from the text, the state of the
  62.             // automaton remains zero
  63.             j++;
  64.         }
  65.         else {
  66.              //we try to "expand" the next best (largest) match
  67.             i = failure[i];
  68.         }
  69.     }
  70.   }
  71.   return false;
  72. }
  73.  
  74. int main(){
  75.     ios::sync_with_stdio(false);
  76.     cin.tie(0);
  77.     cout.tie(0);
  78.     //freopen("output.txt","w",stdout);
  79.     int n;
  80.     cin>>n;
  81.  
  82.     int t;
  83.     cin>>t;
  84.     string a;
  85.     cin>>a;
  86.     for(int tt=0;tt<t;tt++){
  87.         string b;
  88.         cin>>b;
  89.         cnt=0;
  90.         bool bl=kmp(a,b);
  91.  
  92.         cout<<cnt<<"\n";
  93.     }
  94. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top