Pagini recente » Cod sursa (job #1540050) | Cod sursa (job #926018) | Cod sursa (job #2950038) | Cod sursa (job #704699) | Cod sursa (job #501766)
Cod sursa(job #501766)
#include <stdio.h>
#include <string.h>
int n,m,v[2000001],s[1001],sol;
char a[2000001],b[2000001];
void rni()
{
a[0]=' ';scanf("%s",a+1);n=strlen(a)-1;
b[0]=' ';scanf("%s",b+1);m=strlen(b)-1;
}
void prefix()
{
int i,p=0;
for (i=2;i<=n;++i)
{
while (p&&(a[i]!=a[p+1])) p=v[p];
if (a[i]==a[p+1])
{
++p;
v[i]=p;
}
}
}
void kmp()
{
int i,p=0;
for (i=1;i<=m;++i)
{
while (p&&(b[i]!=a[p+1])) p=v[p];
if (b[i]==a[p+1])
{
++p;
if (p==n)
{
++sol;
if (sol<1001) s[sol]=i-p;
}
}
}
}
void w()
{
int i;
printf("%d\n",sol);
if (sol>1000) sol=1000;
for (i=1;i<=sol;++i) printf("%d ",s[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
rni();
prefix();
kmp();
w();
return 0;
}