Pagini recente » Cod sursa (job #1454005) | Cod sursa (job #1321548) | Cod sursa (job #106052) | Istoria paginii runda/pa-test1-2019-22/clasament | Cod sursa (job #235780)
Cod sursa(job #235780)
# include <stdio.h>
# include <string.h>
# define nmax 2000002
char A[nmax],B[nmax];
int Prefix[nmax], p[1024];
long n,m;
void prefix(void)
{
int k=-1;
long i;
Prefix[0]=-1;
for (i=1;i<n;i++)
{
while (k>-1 && A[k+1]!=A[i])
k=Prefix[k];
if (A[k+1]==A[i]) k++;
Prefix[i]=k;
}
}
int main(){
long i,k,j=0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(A); n=strlen(A);
gets(B); m=strlen(B);
prefix();
k=-1;
for (i=0;i<m;i++){
while (k>-1 && A[k+1]!=B[i]) k=Prefix[k];
if (A[k+1]==B[i]) k++;
if (k==n-1){
k=Prefix[n-1],j++;
if (j<=100) p[j]=i-n+1;
}
}
printf("%ld\n",j);
if (j>1000) j=1000;
for (i=1;i<=j;i++)
printf("%ld ", p[i]);
return 0;
}