Pagini recente » Cod sursa (job #2951006) | Cod sursa (job #2127302) | Cod sursa (job #1616314) | Cod sursa (job #408331) | Cod sursa (job #507953)
Cod sursa(job #507953)
#include <stdio.h>
#include <string.h>
int m,n,i,k,L[2000005],v[1002],sol=0;
char Str[2000005],Pat[2000005];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(Pat+1,2000005,stdin);
fgets(Str+1,2000005,stdin);
Pat[0]='!';
Str[0]='!';
m=strlen(Pat)-1;
n=strlen(Str)-1;
if(Pat[m]=='\n') m--;
if(Str[n]=='\n') n--;
for(i=1;i<=102;i++) L[i]=0;
L[1]=0;
for(i=2;i<=m;i++)
{
while(k>0&&Pat[k+1]!=Pat[i]) k=L[k];
if(Pat[k+1]==Pat[i]) k++;
L[i]=k;
}
sol=0;
for(i=1;i<=n;i++)
{
while(k>0&&Str[i]!=Pat[k+1]) k=L[k];
if(Pat[k+1]==Str[i]) k++;
if(k==m)
{
sol++;
if(sol<=1000) v[sol]=i-k;
k=L[k];
}
}
printf("%d\n",sol);
if(sol>1000) sol=1000;
for(i=1;i<=sol;i++)
printf("%d ",v[i]);
printf("\n");
return 0;
}