Pagini recente » Cod sursa (job #2405887) | Cod sursa (job #990215) | Cod sursa (job #1323839) | Cod sursa (job #55132) | Cod sursa (job #440555)
Cod sursa(job #440555)
#include <cstdio>
#include <cstring>
#include <string>
#define nmax 2000005
#define unmax 10005
using namespace std;
char a [nmax], b [nmax];
int urm [nmax], sol [unmax], cnt, n, m;
void prefix ()
{
int i, k;
k = 0;
for (i = 2; i <= n; i++)
{
while (k > 0 && a [k + 1] != a [i])
k = urm [k];
if (a [k + 1] == a [i])
++k;
urm [i] = k;
}
}
void kmp ()
{
int i, k;
k = 0;
for (i = 1; i <= m; i++)
{
while (k > 0 && a [k + 1] != b [i])
k = urm [k];
if (a [k + 1] == b [i])
++k;
if (k == n)
{
if (cnt < 1000) sol [++cnt] = i - n;
else ++cnt;
}
}
printf ("%d\n", cnt);
for (i = 1; i <= min (cnt, 1000); i++)
printf ("%d ", sol [i]);
}
int main ()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
scanf ("%s\n%s\n", a + 1, b + 1);
n = strlen (a + 1);
m = strlen (b + 1);
prefix ();
kmp ();
return 0;
}