Pagini recente » Cod sursa (job #324883) | Cod sursa (job #700738) | Cod sursa (job #102348) | Cod sursa (job #95951) | Cod sursa (job #685633)
Cod sursa(job #685633)
#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);
n=strlen(a+1);
m=strlen(b+1);
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;
}