Pagini recente » Cod sursa (job #3240814) | Cod sursa (job #2332577) | Cod sursa (job #1583411) | Cod sursa (job #2216867) | Cod sursa (job #2373253)
#include <bits/stdc++.h>
#define maxN 2000002
#define maxS 1000
using namespace std;
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);
int n, m;
char a[maxN], b[maxN];
int pi[maxN];
int sol[maxS + 2];
void pref()
{
pi[0] = -1;
int k = -1;
for (int i = 1; i < n; ++ i)
{
while (k >= 0 && a[i] != a[k + 1])
k = pi[k];
if (a[i] == a[k + 1])
++ k;
pi[i] = k;
}
}
int main()
{
scanf("%s\n", a);
scanf("%s\n", b);
n = strlen(a);
m = strlen(b);
pref();
int k = -1, ans = 0;
for (int i = 0; i < m; ++ i)
{
while (k >= 0 && b[i] != a[k + 1])
k = pi[k];
if (b[i] == a[k + 1])
++ k;
if (k == n - 1 && ans < maxS)
sol[ans ++] = i - n + 1;
else
if (k == n)
++ ans;
}
printf("%d\n", ans);
for (int i = 0; i < maxS && i < ans; ++ i)
printf("%d ", sol[i]);
return 0;
}