Pagini recente » Voteaza Algorel | Cod sursa (job #1275743) | Cod sursa (job #2015083) | Cod sursa (job #1242990) | Cod sursa (job #1727417)
#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <math.h>
#define NMAX 2000005
char str_a[NMAX], str_b[NMAX];
int suffix[NMAX];
int 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) {
j = suffix[j - 1];
}
if (str_a[i] == str_a[j])
++j;
suffix[i] = j;
}
j = 0;
/*for (i = 0; i <= len_a; ++i) {
printf ("%d ", suffix[i]);
}*/
for (i = 0; i < len_b; ++i) {
while (str_b[i] != str_a[j] && j) {
j = suffix[j - 1];
}
if (str_b[i] == str_a[j])
++j;
if (j == len_a) {
ans[ans_ind++] = i - len_a + 1;
j = suffix[j - 1];
}
}
int k = _min (ans_ind, 1000);
printf ("%d\n", ans_ind);
for (i = 0; i < k; ++i) {
printf ("%d ", ans[i]);
}
}