Pagini recente » Cod sursa (job #2851948) | Cod sursa (job #2648896) | Cod sursa (job #1514696) | Cod sursa (job #1764050) | Cod sursa (job #359763)
Cod sursa(job #359763)
#include<fstream.h>
#include<string.h>
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long nr,n,m,k,q,i,urm[2000000],v[2000000];
char t[2000000],p[2000000],aux[2000001];
int main()
{f.get(t,20000);
f.get();
f.get(p,20000);
m=strlen(p);
n=strlen(t);
strcpy(aux," ");
strcat(aux,t);
strcpy(t,aux);
strcpy(aux," ");
strcat(aux,p);
strcpy(p,aux);
urm[1]=0;
k=0;
for(q=2;q<=m;q++)
{while(k>0&&p[k+1]!=p[q])
k=urm[k];
if(p[k+1]==p[q])
k++;
urm[q]=k;
}
q=0;
nr=0;
for(i=1;i<=n;i++)
{while(q>0&&p[q+1]!=t[i])
q=urm[q];
if(p[q+1]==t[i])
q++;
if(q==m)
{nr++;
v[nr]=i-m;
q=urm[q];}
}
g<<nr<<'\n';
for(i=1;i<nr;i++)
g<<v[i]<<' ';
g<<v[nr]<<'\n';
f.close();
g.close();
return 0;
}