Pagini recente » Cod sursa (job #1859977) | Cod sursa (job #578561) | Cod sursa (job #2397278) | Cod sursa (job #466130) | Cod sursa (job #1688977)
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 2000050
using namespace std;
char a[MAXN], b[MAXN];
int pre[MAXN], n, m, sol[1050], nq;
void prefix()
{
int pi = 0;
for (int i = 2; i <= n; i++) {
while (pi && a[i] != a[pi+1])
pi = pre[pi];
if (a[i] == a[pi+1])
pi++;
pre[i] = pi;
}
}
void solutie(int ind)
{
++nq;
if (nq <= 1000)
sol[nq] = ind;
}
void solve()
{
int pi = 0;
for (int i = 1; i <= m; i++) {
while (pi && b[i] != a[pi+1])
pi = pre[pi];
if (b[i] == a[pi+1])
pi++;
if (pi >= n)
solutie(i);
}
}
void afisare()
{
printf("%d\n", nq);
for (int i = 1; i <= min(1000, nq); i++)
printf("%d ", sol[i]-n);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
a[0] = b[0] = ' ';
fgets(a+1, MAXN, stdin);
n = strlen(a)-1;
a[n--] = 0;
fgets(b+1, MAXN, stdin);
m = strlen(b)-1;
b[m--] = 0;
prefix();
solve();
afisare();
return 0;
}