Pagini recente » Cod sursa (job #482129) | Cod sursa (job #537589) | Cod sursa (job #1092175) | Cod sursa (job #2181768) | Cod sursa (job #1726940)
#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) {
if (str_a[i] == str_a[j]) {
suffix[i] = ++j;
}
else {
while (suffix[i] != suffix[j] && j != 0) {
j = suffix[j - 1];
}
}
}
j = 0;
int go_until = _min(len_b, 1000);
for (i = 0; i < go_until; ++i) {
if (str_a[j] == str_b[i]) {
++j;
}
else {
while (str_a[j] != str_b[i] && j != 0) {
j = suffix[j - 1];
}
}
if (j == len_a) {
ans[ans_ind++] = i - len_a + 1;
j = suffix[j - 1];
}
}
printf ("%d\n", ans_ind);
for (i = 0; i < ans_ind; ++i) {
printf ("%d ", ans[i]);
}
}