Pagini recente » Cod sursa (job #1770923) | Cod sursa (job #2926188) | Cod sursa (job #537534) | Cod sursa (job #2801297) | Cod sursa (job #1712422)
//kmp algorithm
#include <stdio.h>
#include <string.h>
char p[2000009],txt[2000009];
int f[2000009],n,m,i,k,j,sol[1024];
void getphi()
{
f[0]=0;
int k=0;
for (int i=1;i<n;++i)
{
while (k>0 && p[k]!=p[i])
k=f[k-1];
if (p[k]==p[i])
k++;
f[i]=k;
}
}
int main()
{
freopen("strmathc.in","r",stdin);
freopen("strmathc.out","w",stdout);
scanf("%s",p);
scanf("%s",txt);
n=strlen(p);
m=strlen(txt);
getphi();
k=0;
j=0;
for (i=0;i<m;++i)
{
while (j>0 && p[j]!=txt[i])
j=f[j-1];
if (txt[i]==p[j])
j++;
if (j==n)
{
if (k<1000)
sol[k]=i-n+1;
k++;
}
}
printf("%d\n",k);
for (i=0;i<(k<1000 ? k : 1000);++i)
printf("%d ",sol[i]);
return 0;
}