Pagini recente » Cod sursa (job #1497343) | Cod sursa (job #2313645) | Cod sursa (job #963516) | Cod sursa (job #1223860) | Cod sursa (job #170044)
Cod sursa(job #170044)
#include<stdio.h>
#include<string.h>
#define NMAX 2000010
#define MMAX 1010
int q,s[MMAX];
void prekmp(char *x, int m, int k[])
{
int i,j;
i=0;
j=k[0]=-1;
while (i<m)
{
while (j>-1&&x[i]!=x[j])
j=k[j];
i++, j++;
if (x[i]==x[j])
k[i]=k[j];
else
k[i]=j;
}
}
void kmp(char *x, int m, char *y, int n)
{
int i,j,k[MMAX];
prekmp(x,m,k);
i=j=0;
while (i<n)
{
while(j>-1&&x[j]!=y[i])
j=k[j];
i++,j++;
if (j>=m)
{
q++;
if (q<=1000)
s[q]=i-j;
j=k[j];
}
}
}
void afis()
{
printf("%d\n",q);
for (int i=1;i<=q&&i<=1000;i++)
printf("%d ",s[i]);
printf("\n");
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int n,m;
char a[NMAX],b[NMAX];
gets(a);
gets(b);
m=strlen(a);
n=strlen(b);
kmp(a,m,b,n);
afis();
return 0;
}