Pagini recente » Cod sursa (job #160153) | Istoria paginii jc2020/solutii/papagali | Cod sursa (job #1150018) | Cod sursa (job #884014) | Cod sursa (job #1726944)
#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <math.h>
#define NMAX 2000001
char str_a[NMAX], str_b[NMAX];
int suffix[NMAX];
short ans[NMAX];
int _min (int a, int b) {
return a < b ? a : b;
}
int main () {
int i, j, ans_ind = 0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf ("%s", str_a);
scanf ("%s", str_b);
int len_a = strlen(str_a),
len_b = strlen(str_b);
j = 0;
for (i = 1; i < len_a; ++i) {
while (str_a[i] != str_a[j] && j != 0) {
j = suffix[j - 1];
}
if (str_a[i] == str_a[j])
suffix[i] = ++j;
else
suffix[i] = 0;
++j;
}
j = 0;
int go_until = _min(len_b, 1000);
for (i = 0; i < go_until; ++i) {
while (str_b[i] != str_a[j] && j != 0) {
j = suffix[j - 1];
}
if (str_b[i] == str_a[j])
++j;
if (j == len_a) {
ans[ans_ind++] = i - len_a + 1;
}
}
printf ("%d\n", ans_ind);
for (i = 0; i < ans_ind; ++i) {
printf ("%d ", ans[i]);
}
}