Cod sursa(job #408362)
#include <stdio.h>
#include<string.h>
using namespace std;
#define millions 2000001
#define thousand 1001
char P[millions], T[millions];
int prefx[millions], D[thousand];
int n, m;
void found(int d)
{
D[0]++;
if (D[0] <= 1000)
{
D[D[0]] = d;
}
}
void citire()
{
freopen("strmatch.in", "r", stdin);
P[0] = T[0] = ' ';
gets(P+1);
gets(T+1);
}
void prefix(char P[])
{
int p, k;
prefx[1] = 0;
for (p = 2; p <= m; p++)
{
k = prefx[p-1];
while (k > 0 && P[k+1] != P[p])
{
k = prefx[k];
}
if (P[k+1] == P[p])
{
k = k+1;
}
prefx[p] = k;
}
}
void knuth_morris_pratt(char P[], char T[])
{
int t, k;
prefix(P);
for (k = 0, t = 1; t <= n; ++t)
{
while (k > 0 && P[k+1] != T[t])
{
k = prefx[k];
}
if (P[k+1] == T[t])
{
k = k+1;
}
if (k == m)
{
found(t-m);
k = prefx[k];
}
}
}
void afisare()
{
int i;
freopen("strmatch.out", "w", stdout);
printf("%d\n", D[0]);
for (i = 1; i <= 1000 && i <= D[0]; ++i)
printf("%d ", D[i]);
}
int main()
{
citire();
for (m = -1; P[m+1]; ++m);
for (n = -1; T[n+1]; ++n);
knuth_morris_pratt(P, T);
afisare();
return 0;
}