Pagini recente » Cod sursa (job #1074442) | Cod sursa (job #609666) | Cod sursa (job #1345116) | Cod sursa (job #1227072) | Cod sursa (job #314355)
Cod sursa(job #314355)
#include <stdio.h>
#include <string.h>
#define dim 2000001
char a[dim], b[dim], match[dim];
int na, nb, phi[dim], ct=0;
void prefix()
{
int k=0, q;
phi[1]=0;
for (q=2; q<=na; q++)
{
while (k && a[k+1]!=a[q]) k=phi[k];
if (a[k+1]==a[q]) k++;
phi[q]=k;
}
}
void kmp()
{
int q=0, i;
for (i=1; i<=nb; i++)
{
while (q && a[q+1]!=b[i])
q=phi[q];
if (a[q+1]==b[i]) q++;
if (q==na) match[i-na]=1, ct++;
}
}
int main()
{
int i;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s\n", a+1, b+1);
na=strlen(a+1);
nb=strlen(b+1);
prefix();
kmp();
printf("%d\n", ct);
ct=0;
for (i=0; i<nb && ct<1000; i++)
if (match[i])
{
printf("%d ", i);
ct++;
}
printf("\n");
return 0;
}