@zzzc18
2017-11-09T11:39:50.000000Z
字数 656
阅读 1011
模板库
字符串
数组究竟是什么?
即对于当前位置 ,模式串在 和 的部分完全相同
匹配的复杂度为 (这里不带证明)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1000000+9;
char T[MAXN],P[MAXN];
int next[MAXN];
void GetFail(char *S){
int len=strlen(S);
for(int i=1;i<len;i++){
int loc=next[i];
while(loc && S[loc]!=S[i]){
loc=next[loc];
}
next[i+1]=(S[loc]==S[i])?loc+1:0;
}
}
void solve(){
GetFail(P);
int len=strlen(T);
int goal=strlen(P);
int loc=0;
for(int i=0;i<len;i++){
while(loc && T[i]!=P[loc])
loc=next[loc];
if(T[i]==P[loc])
loc++;
if(loc==goal)
printf("%d\n",i+1-goal+1);
}
for(int i=1;i<=goal;i++)
printf("%d ",next[i]);
}
int main(){
scanf("%s%s",T,P);
solve();
return 0;
}