Pagini recente » Cod sursa (job #1692880) | Cod sursa (job #2180350) | Cod sursa (job #1050263) | Cod sursa (job #1886570) | Cod sursa (job #1315239)
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
char S[2000001],P[2000001];
int pi[2000001],v[2000001],n,m;
void preprocesare(){
pi[0]=0;
int k=0;
for(int q=1;q<m;q++){
while((k>0)&&P[k]!=P[q])
k=pi[k-1];
if(P[k]==P[q])
k++;
pi[q]=k;
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",&P,&S);
m=strlen(P);
n=strlen(S);
preprocesare();
int q=0,cate=0;;
for(int i=0;i<n;i++){
while((q>0)&&(P[q]!=S[i])){
q=pi[q-1];
}
if(P[q]==S[i]){
q++;
}
if(q==m){
if(cate<1000){
cate++;
v[cate]=i-m+1;
}
}
}
printf("%d\n",cate);
for(int i=1;i<=cate;i++)
printf("%d ",v[i]);
return 0;
}