Pagini recente » Cod sursa (job #2167287) | Cod sursa (job #1798186) | Cod sursa (job #3261667) | Cod sursa (job #2186210) | Cod sursa (job #440546)
Cod sursa(job #440546)
#include <cstdio>
#include <cstring>
#define nmax 2000005
#define unmax 10005
using namespace std;
char a [nmax], b [nmax];
int urm [unmax], 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)
{
sol [++cnt] = i - n;
if (cnt == 1000) break;
}
}
printf ("%d\n", cnt);
for (i = 1; i <= cnt; 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;
}