Pagini recente » Cod sursa (job #2388575) | Cod sursa (job #1903377) | Cod sursa (job #1458597) | Cod sursa (job #1089824) | Cod sursa (job #316771)
Cod sursa(job #316771)
#include<stdio.h>
#define N 2000005
char a[N],b[N];
int n,m,num,v[1001],p[N],k;
void pi()
{
p[1]=0;
k=0;
for (int i=2; i<=n; ++i)
{
while (k&&a[k+1]!=a[i])
k=p[k];
if (a[k+1]==a[i]) ++k;
p[i]=k;
}
}
void kmp()
{
k=0;
for (int i=1; i<=m; ++i)
{
while (k&&a[k+1]!=b[i])
k=p[k];
if (a[k+1]==b[i])++k;
if (k==n)
{
++num;
if (num<=1000)
v[num]=i-n;
k=p[n];
}
}
}
void afis()
{
printf("%d\n",num);
for (int i=1; i<=num; ++i)
{
printf("%d ",v[i]);
if (i>=1000)
return;
}
}
void citire()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,N-1,stdin);
fgets(b,N-1,stdin);
while (a[n])++n;--n;
while (b[m])++m; --m;
for (int i=n; i; --i) a[i]=a[i-1];
for (int i=m; i; --i) b[i]=b[i-1];
a[0]=b[0]=' ';
pi();
kmp();
}
int main()
{
citire();
afis();
return 0;
}