Pagini recente » Cod sursa (job #2519753) | Cod sursa (job #1842621) | Cod sursa (job #2613811) | Cod sursa (job #1272465) | Cod sursa (job #330706)
Cod sursa(job #330706)
#include<stdio.h>
#include<string.h>
#define nmax 2000010
char a[nmax],b[nmax];
long k[nmax],n,m,nr,poz[1010];
void read()
{
scanf("%s",a);
scanf("%s",b);
n=strlen(b);
m=strlen(a);
}
void border()
{
long i,j;
i=0;
j=-1;
k[0]=-1;
while (i<m)
{
while (j>=0 && a[j]!=a[i])
j=k[j];
i++;
j++;
if (a[i]==a[j])
k[i]=k[j];
else k[i]=j;
}
}
void kmp()
{
long i,j;
i=j=0;
while (i<n)
{
while (j>=0 && b[i]!=a[j])
j=k[j];
i++;j++;
if (j>=m)
{
nr++;
if (nr<=1000)
poz[++poz[0]]=i-j;
j=k[j];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
border();
kmp();
printf("%ld\n",nr);
long i;
for (i=1;i<=poz[0];i++)
printf("%ld ",poz[i]);
return 0;
}