Pagini recente » Cod sursa (job #3232391) | Cod sursa (job #842825) | Cod sursa (job #542808) | Cod sursa (job #529262) | Cod sursa (job #1770642)
#include <stdio.h>
#include <string.h>
enum {
NMAX = 2000000
};
char a[1 + NMAX + 1];
char b[1 + NMAX + 1];
int pi[1 + NMAX];
int *build_prefix(char *a, int l1, int *pi) {
pi[1] = 0;
int pos = 0;
for (int i = 2; i <= l1; ++i) {
while (pos > 0 && a[pos + 1] != a[i])
pos = pi[pos];
if (a[pos + 1] == a[i])
++pos;
pi[i] = pos;
}
return pi;
}
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_prefix(a, l1, pi);
int match_count = 0;
int solutions[1001];
int pos = 0;
for (int i = 1; i <= l2; ++i) {
while (pos > 0 && a[pos + 1] != b[i])
pos = pi[pos];
if (a[pos + 1] == b[i])
++pos;
if (pos == 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;
}