NgJaBach

String Matching

Jul 22nd, 2020
193
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N=100005;
  5. void KMP(){
  6.     int i,j,table[N],n,m;
  7.     string a,b;
  8.     fflush(stdin); cin>>a; n=a.size();
  9.     fflush(stdin); cin>>b; m=b.size();
  10.     table[0]=0; i=0;
  11.     for(j=1;j<m;++j){
  12.         if(b[i]==b[j]){
  13.             ++i;
  14.             table[j]=i;
  15.         }
  16.         else{
  17.             i=0;
  18.             table[j]=i;
  19.         }
  20.     }
  21.     i=0; j=0;
  22.     while(i<n){
  23.         if(a[i]==b[j]){
  24.             ++j; ++i;
  25.             if(j==m){
  26.                 cout<<i-j+1<<" ";
  27.                 j=table[j-1];
  28.             }
  29.         }
  30.         else{
  31.             if(j==0) ++i;
  32.             else j=table[j-1];
  33.         }
  34.     }
  35. }
  36. int main(){
  37.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(NULL);
  38.     KMP();
  39.     return 0;
  40. }
RAW Paste Data Copied