SUBSTR - Xâu con

Tác giả: hieult

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1111111111
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

void KMP(string text,string pattern){
      int n = text.length(), m = pattern.length(), F[m+2],i,j;
      F[0] = F[1] = 0;
      for(int i = 2;i<=m;i++){
           j = F[i-1];
           while(true){
                if(pattern[j] == pattern[i-1]) { F[i] = j+1; break;}
                else if(j==0) {F[i] = 0; break;}
                else j = F[j];
           }
      }
      
      i = j = 0;
      while(j<n){
           if(text[j] == pattern[i]){
                i++; j++;
                if(i==m) printf("%d ",j-i+1);
           }
           else if(i>0) i = F[i];
           else j++;
      }
}

int main(){
     string a,b;
     cin>>a>>b;
     KMP(a,b);
    // getch();  
}

Download