Pagini recente » Cod sursa (job #320645) | Cod sursa (job #186836) | Cod sursa (job #2255186) | Cod sursa (job #299684) | Cod sursa (job #1552545)
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000010], b[2000010];
int phi[2000010], Phi[2000010], rez[1024];
int main ()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
gets (b + 1);
gets (a + 1);
int m = strlen (b + 1), n = strlen (a + 1);
for (int i = 2; i <= m; ++i)
{
int k = phi[i - 1];
while (k && b[i] != b[k + 1])
k = phi[k];
if (b[i] == b[k + 1]) phi[i] = k + 1;
}
b[m + 1] = ' ';
int p = 0;
for (int i = 1; i <= n; ++i)
{
int k = Phi[i - 1];
while (k && a[i] != b[k + 1])
k = phi[k];
if (a[i] == b[k + 1]) Phi[i] = k + 1;
if (Phi[i] == m)
{
++p;
if (p <= 1000) rez[p] = i - m;
}
}
printf ("%d\n", p);
for (int i = 1; i <= p; ++i)
printf ("%d ", rez[i]);
printf ("\n");
return 0;
}