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();
}