Pagini recente » Clasament hlo-2023-cls1112-tema0 | Cod sursa (job #678440) | Cod sursa (job #1520552) | Istoria paginii preoni-2007/clasament/runda-4/9 | Cod sursa (job #1764025)
#include <cstdio>
#include <string.h>
using namespace std;
int pi[2000010], poz[2000010], i, k, q, n, m, p;
char A[2000010], B[2000010];
int main () {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", A + 1);
scanf("%s", B + 1);
n = strlen(A + 1);
m = strlen(B + 1);
for (i = 2; i <= n; i++) {
while (k > 0 && A[k + 1] != A[i]) {
k = pi[k];
}
if (A[k + 1] == A[i]) {
k++;
}
pi[i] = k;
}
for (i = 1; i <= m; i++) {
while (q > 0 && A[q + 1] != B[i]) {
q = pi[q];
}
if (A[q + 1] == B[i]) {
q++;
}
if (q == n) {
poz[++p] = i - n;
}
}
printf("%d\n", p);
for (i = 1; i <= p && i <= 1000; i++) {
printf("%d ", poz[i]);
}
return 0;
}