Pagini recente » Cod sursa (job #2899821) | Cod sursa (job #2596416) | Cod sursa (job #2329478) | Cod sursa (job #2067682) | Cod sursa (job #345207)
Cod sursa(job #345207)
#include <stdio.h>
#include <string.h>
#define DIM 2000100
char a[DIM], b[DIM];
int pi[DIM], n, m, nr, p[1024];
void calc_pi()
{
int k=0;
for (int i=2; i<=n; ++i)
{
while (a[i]!=a[k+1] && k>0) k=pi[k];
if (a[k+1]==a[i]) ++k;
pi[i]=k;
}
}
void kmp()
{
int k=0;
for (int i=1; i<=m; ++i)
{
while (a[k+1]!=b[i] && k>0) 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);
fgets(a+1,DIM,stdin);
fgets(b+1,DIM,stdin);
while (a[++n] != '\n');--n;
while (b[++m] != '\n');--m;
calc_pi();
kmp();
printf("%d\n",nr);
for (int i=1; i<=nr && i<=1024; ++i)
printf("%d ",p[i]);
printf("\n");
return 0;
}