Pagini recente » Cod sursa (job #1091050) | Cod sursa (job #1259149) | Cod sursa (job #2833935) | Cod sursa (job #2137852) | Cod sursa (job #779635)
Cod sursa(job #779635)
#include <stdio.h>
#include <string.h>
#define NMax 2000010
const char IN[]="strmatch.in",OUT[]="strmatch.out";
int N,M;
int P[NMax],Rez[1010];
char A[NMax],B[NMax];
void prefix(){
int i,k=0;
P[1]=k;
for (i=2;i<=N;++i)
{
while (k>0 && A[k+1]!=A[i])
k=P[k];
if (A[k+1]==A[i])
++k;
P[i]=k;
}
}
void solve(){
int i,k=0;
for (i=1;i<=M;++i)
{
while (k>0 && A[k+1]!=B[i])
k=P[k];
if (A[k+1]==B[i])
++k;
if (k==N)
{
++Rez[0];
if (Rez[0]>1000) continue;
Rez[Rez[0]]=i-N;
}
}
}
int main()
{
int i;
freopen(IN,"r",stdin);
scanf("%s%s",A+1,B+1);
fclose(stdin);
N=strlen(A+1);M=strlen(B+1);
prefix();
solve();
freopen(OUT,"w",stdout);
printf("%d\n",Rez[0]);
for (i=1;i<=Rez[0] && i<1001;++i) printf("%d ",Rez[i]); printf("\n");
fclose(stdout);
return 0;
}