Pagini recente » Cod sursa (job #2326061) | Cod sursa (job #323169) | Cod sursa (job #864681) | Cod sursa (job #1820387) | Cod sursa (job #345202)
Cod sursa(job #345202)
#include <stdio.h>
#include <string.h>
#define DIM 2000005
char a[DIM], b[DIM];
int pi[DIM], n, m, nr, p[1024];
void calc_pi()
{
int k;
for (int i=2; i<=n; ++i)
{
while (a[i]!=a[k+1] && k) k=pi[k];
if (a[k+1]==a[i]) ++k;
pi[i]=k;
}
}
void kmp()
{
int k;
for (int i=2; i<=m; ++i)
{
while (a[k+1]!=b[i] && k) k=pi[k];
if (a[k+1]==b[i]) ++k;
if (k==n)
{
++nr;
if (nr<=1024) p[nr]=i-n;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a+1); n=strlen(a+1);
gets(b+1); m=strlen(b+1);
calc_pi();
kmp();
printf("%d\n",nr);
for (int i=1; i<=nr && i<=1024; ++i)
printf("%d ",p[i]);
printf("\n");
return 0;
}