Pagini recente » Cod sursa (job #2907694) | Cod sursa (job #1770609)
#include <stdio.h>
#include <string.h>
enum {
NMAX = 2000000
};
char a[NMAX];
char b[NMAX];
int kmp[NMAX];
int *build_kmp(char *a, char *b, int l1, int l2, int *kmp) {
memset(kmp, 0, sizeof(kmp));
int pos = 0;
for (int i = 1; i <= l2; ++i) {
while (a[pos + 1] != b[i] && pos > 0)
pos = kmp[pos];
if (a[pos + 1] == b[i])
++pos;
kmp[i] = pos;
}
return kmp;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", a + 1, b + 1);
int l1 = strlen(a + 1);
int l2 = strlen(b + 1);
build_kmp(a, b, l1, l2, kmp);
int match_count = 0;
int solutions[1001];
for (int i = 1; i <= l2; ++i)
if (kmp[i] == l1)
solutions[++match_count] = i;
printf("%d\n", match_count);
for (int i = 1; i <= match_count && i <= 1000; ++i)
printf("%d ", solutions[i] - l1);
printf("\n");
return 0;
}