Pagini recente » Cod sursa (job #2497455) | Cod sursa (job #1960002) | Cod sursa (job #629626) | Cod sursa (job #953249) | Cod sursa (job #1091748)
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define NMAX 2000010
int n, m, num;
int table[NMAX];
char w[NMAX], s[NMAX];
queue <int> sol;
void ReadData ()
{
scanf ("%s \n %s", w, s);
n = strlen (s);
m = strlen (w);
w[m] = '#';
}
void Init_Table ()
{
table[0] = -1;
int i = 2, k = 0;
while (i <= m)
if (w[i - 1] == w[k])
{
++k;
table[i] = k;
++i;
}
else if (k)
k = table[k];
else
{
table[i] = 0;
++i;
}
}
void KMP ()
{
int k = 0;
for (int i = 0; k + i < n; )
{
if (s[k + i] == w[i])
{
if (i == m - 1)
{
++num;
if (num <= 1000)
sol.push(k);
}
++i;
}
else
{
k += i - table[i];
i = (table[i] > -1) ? table[i] : 0;
}
}
}
int main ()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
ReadData();
if (m > n) {printf ("0"); return 0;}
Init_Table();
KMP ();
printf ("%d\n", num);
while (!sol.empty())
{
printf ("%d ", sol.front());
sol.pop();
}
return 0;
}