Pagini recente » Cod sursa (job #1619758) | Cod sursa (job #1031409) | Cod sursa (job #2629541) | Cod sursa (job #633392) | Cod sursa (job #392263)
Cod sursa(job #392263)
#include<stdio.h>
#define Nmax 2000000
char A[Nmax],B[Nmax];
int pi[Nmax],pos[1024];
int N,M;
void prefix(void)
{int q=0,i=0;
for(i=2,pi[1]=0;i<=M;++i)
{while(q && A[q+1]!=A[i])
q=pi[q];
if(A[q+1]==A[i])
++q;
pi[i]=q;
}
}
int main()
{freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(A,sizeof(A),stdin);
fgets(B,sizeof(B),stdin);
while((A[M] >= 'A' && A[M] <= 'Z') || (A[M] >= 'a' && A[M] <= 'z')|| (A[M] >= '0' && A[M] <= '9'))
++M;
while((B[N] >= 'A' && B[N] <= 'Z') || (B[N] >= 'a' && B[N] <= 'z')|| (B[N] >= '0' && B[N] <= '9'))
++N;
int i;
for(i=M;i>0;i--) A[i]=A[i-1]; A[0]=' ';
for(i=N;i>0;i--) B[i]=B[i-1]; B[0]=' ';
int q=0,n=0;
prefix();
for(i=1;i<=N;++i)
{ while(q && A[q+1]!=B[i])
q=pi[q];
if(A[q+1]==B[i])
++q;
if(q==M)
{q=pi[M];
++n;
if(n<=1000)
pos[n]=i-M;
}
}
printf("%d\n ",n);
if(n>1000)
n=1000;
for(i=1;i<=n;i++)
printf("%d ",pos[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;}