Pagini recente » Cod sursa (job #2124366) | Cod sursa (job #1283574) | Profil florinhaja | Cod sursa (job #2366449) | Cod sursa (job #548466)
Cod sursa(job #548466)
#include<stdio.h>
#include<string.h>
#define Nmax 2000009
int nr,q,i,j,n,m,a[Nmax],b[1000];
char s1[Nmax],s2[Nmax];
void prefix()
{
q=0;
a[0]=0;
for (i=1;i<n;i++)
{
while (q>0&&s1[q]!=s1[i])
q=a[q-1];
if (s1[q]==s1[i])
q++;
a[i]=q;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s1);
gets(s2);
n=strlen(s1);m=strlen(s2);
prefix();
q=0;i=0;
for (i=0;i<m;i++)
{
while(q>0 && s1[q]!=s2[i])
q=a[q-1];
if(s1[q]==s2[i])
q++;
if (q==n)
{
q=a[q-1];
nr++;
if (nr<=1000) b[nr]=i-n+1;
}
}
printf("%d\n",nr);
if (nr>1000) nr=1000;
for (i=1;i<=nr;i++)
printf("%d ",b[i]);
printf("\n");
return 0;
}