Pagini recente » Cod sursa (job #2180866) | Cod sursa (job #2405712) | Cod sursa (job #2748087) | Monitorul de evaluare | Cod sursa (job #779631)
Cod sursa(job #779631)
#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[++Rez[0]]=i-N;
if (Rez[0]>=1000) return;
}
}
}
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) printf("%d ",Rez[i]); printf("\n");
fclose(stdout);
return 0;
}