Pagini recente » Cod sursa (job #2744196) | Cod sursa (job #236600) | Cod sursa (job #3156334) | Cod sursa (job #2854216) | Cod sursa (job #301201)
Cod sursa(job #301201)
#include<stdio.h>
#include<string.h>
#define Nmax 2000002
char T[Nmax],P[Nmax];
int m,n,v[1010],pi[Nmax];
void prefix()
{
int k=0,i;
for(i=2;i<=n;++i)
{
while (k>0 && T[k+1]!=T[i])
k=pi[k];
if (T[k+1]==T[i])
k=k+1;
pi[i]=k;
}
}
void KMP()
{
int i,k=0;
for(i=1;i<=m;++i)
{
while (k>0 && T[k+1]!=P[i])
k=pi[k];
if (T[k+1]==P[i])
k=k+1;
if (k==n)
{
++v[0];
if (v[0]<1000)
v[v[0]]=i-n;
k=pi[k];
}
}
}
int main()
{
int i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",T);
scanf("%s",P);
n=strlen(T); m=strlen(P);
for(i=n;i;--i) T[i]=T[i-1]; T[0]=' ';
for(i=m;i;--i) P[i]=P[i-1]; P[0]=' ';
prefix();
KMP();
printf("%d\n",v[0]);
if (v[0]>1000) v[0]=1000;
for(i=1;i<=v[0];++i)
printf("%d ",v[i]);
printf("\n");
return 0;
}