Cod sursa(job #792754)
#include <cstdio>
#include <cstring>
#define LGMAX 2000003
using namespace std;
FILE *inFile = fopen ("strmatch.in", "r");
FILE *outFile = fopen ("strmatch.out", "w");
int na;
int nb;
int pref[LGMAX];
int res[LGMAX];
char a[LGMAX];
char b[LGMAX];
void prefix()
{
int i = 0;
int j = -1;
pref[i] = j;
while (i < na)
{
while (j >= 0 && a[i] != a[j])
j = pref[j];
++i;
++j;
pref[i] = j;
}
}
void kmp()
{
int i = 0;
int j = 0;
while (i < nb)
{
while (j >= 0 && b[i] != a[j])
j = pref[j];
++i;
++j;
if (j == na)
{
res[++res[0]] = i - j;
j = pref[j];
}
}
}
void result()
{
fprintf (outFile, "%d\n", res[0]);
if (res[0] > 1000)
res[0] = 1000;
for (int i = 1; i <= res[0]; ++i)
fprintf (outFile, "%d ", res[i]);
fprintf (outFile, "\n");
}
int main()
{
fgets (a, LGMAX, inFile);
fgets (b, LGMAX, inFile);
na = strlen (a) - 1;
nb = strlen (b) - 1;
if (na > nb)
{
fprintf (outFile, "0\n");
return 0;
}
prefix();
kmp();
result();
return 0;
}