Pagini recente » Cod sursa (job #464658) | Cod sursa (job #477377) | Cod sursa (job #491600) | Cod sursa (job #2822299) | Cod sursa (job #877998)
Cod sursa(job #877998)
#include<fstream>
#include<string.h>
#define dim 2000008
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char N[dim],M[dim];
int n,m,k,q,p[dim],ans[1024],nr,i;
int main () {
f>>(N+1);
f>>(M+1);
//prefix
n=strlen(N+1);
m=strlen(M+1);
k=0;
p[1]=0;
for(i=2;i<=n;++i){
while( k>0 && N[k+1]!=N[i] ){
k=p[k];
}
if(N[k+1]==N[i])
++k;
p[i]=k;
}
q=0;
for(i=1;i<=m;++i){
while(q>0 && N[q+1]!=M[i]){
q=p[q];
}
if(N[q+1]==M[i])
++q;
if(q==n){
if(nr<=1000){
ans[++nr]=i-q;
}
}
}
g<<nr<<"\n";
for(i=1;i<=nr;++i)
g<<ans[i]<<" ";
return 0;
}