Pagini recente » Cod sursa (job #3172481) | Cod sursa (job #1879921) | Cod sursa (job #710405) | Cod sursa (job #360903)
Cod sursa(job #360903)
#include<stdio.h>
#include<string.h>
char m[2000100],n[2000100];
int i,k,ln,lm,pi[2000100],p[1010];
long long nr;
void prefix()
{ int k=0;
pi[1]=0;
for(i=2;i<=ln;i++) { while(k>0&&n[k+1]!=n[i]) k=pi[k];
if(n[k+1]==n[i]) k++;
pi[i]=k;
}
}
void kmp()
{
int k=0;
for(i=1;i<=lm;i++) { while(k>0&&n[k+1]!=m[i]) k=pi[k];
if(n[k+1]==m[i]) k++;
if(k==ln) { nr++;
if(nr<=1000) p[nr]=i-ln;
}
}
printf("%d\n",nr);
if(nr>1000) nr=1000;
for(i=1;i<=nr;i++) printf("%d ",p[i]);
printf("\n");
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",n+1);
scanf("%s",m+1);
ln=strlen(n+1);
lm=strlen(m+1);
if(n[ln]=='\n') ln--;
if(m[lm]=='\n') lm--;
prefix();
kmp();
fclose(stdin);
fclose(stdout);
return 0;
}