Pagini recente » Cod sursa (job #490563) | Cod sursa (job #2483102) | Cod sursa (job #2699081) | Cod sursa (job #2539882) | Cod sursa (job #685634)
Cod sursa(job #685634)
#include<stdio.h>
#include<fstream>
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
int nr,n,m,v[1001],p[2000004];
char a[2000004],b[2000004];
void prep()
{
int k=0;
p[1]=0;
for(int i=2;i<=n;++i)
{
while(k&&a[i]!=a[k+1])
k=p[k];
if(a[i]==a[k+1])
++k;
p[i]=k;
}
}
void kmp()
{
int q=0;
for(int i=1;i<=m;++i)
{
while(q&&b[i]!=a[q+1])
q=p[q];
if(b[i]==a[q+1])
++q;
if(q==n)
{
++nr;
if(nr<=1000)
v[nr]=i-n;
}
}
}
int main()
{
fscanf(f,"%s",a+1);
fscanf(f,"\n");
fscanf(f,"%s",b+1);
for(n=1;a[n];++n);
--n;
for(m=1;b[m];++m);
--m;
prep();
kmp();
fprintf(g,"%d\n",nr);
if(nr>1000)
nr=1000;
for(int i=1;i<=nr;++i)
fprintf(g,"%d ",v[i]);
fclose(g);
fclose(f);
return 0;
}