Pagini recente » Cod sursa (job #1931485) | Cod sursa (job #1682973) | Cod sursa (job #1439063) | Cod sursa (job #2749085) | Cod sursa (job #278966)
Cod sursa(job #278966)
#include<stdio.h>
#include<string.h>
#define Nmax 2000003
char A[Nmax], B[Nmax];
int sol[1005];
int nr=0;
int pi[Nmax],n,m;
void read()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n",A);
scanf("%s\n",B);
n=strlen(A);
m=strlen(B);
int i;
for(i=n;i>0;--i) A[i]=A[i-1]; A[0]=' ';
for(i=m;i>0;--i) B[i]=B[i-1]; B[0]=' ';
}
void prefix()
{
int k=0;
int i;
pi[1]=0;
for(i=2;i<=n;++i)
{
while(k && A[k+1] != A[i]) k=pi[k];
if(A[k+1] == A[i]) ++k;
pi[i]=k;
}
}
void kmp()
{
int k=0,i;
for(i=2;i<=m;++i)
{
while(k && A[k+1] != B[i]) k=pi[k];
if(A[k+1] == B[i]) ++k;
if(k==n)
{
++nr;
if(nr<=1000) sol[nr]=i-n;
k=pi[n];
}
}
printf("%d\n",nr);
if(nr>1000) nr=1000;
for(i=1;i<=nr;++i) printf("%d ",sol[i]);
}
int main()
{
read();
prefix();
kmp();
return 0;
}