Pagini recente » Cod sursa (job #559597) | Cod sursa (job #3275858) | Cod sursa (job #1354903) | Cod sursa (job #389462) | Cod sursa (job #500410)
Cod sursa(job #500410)
#include <string.h>
#include <cstdio>
using namespace std;
int F[2000002];
int M, N;
char pattern[2000001];
char text[2000001];
void build_failure(char pattern[]) {
//0...M-1
F[0] = F[1] = 0;
for (int i = 2; i <= M; ++i) {
int j = F[i-1];
while (1) {
if (pattern[j] == pattern[i-1]) {
F[i] = j + 1; break;
}
if (j == 0) {F[i] = 0; break;}
j = F[j];
}
}
}
int v[1024], total;
void kmp(char text[], char pattern[]) {
build_failure(pattern);
int i = 0, j = 0;
while (1) {
if (i == N) break;
if (text[i] == pattern[j]) {
++i;++j;
if (j == M) {
++total;
if (v[0] < 1000)
v[++v[0]] = i - M;
j = F[j];
}
} else {
if (j > 0) j = F[j];
else ++i;
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", &pattern, &text);
N = strlen(text); M = strlen(pattern);
kmp(text, pattern);
printf("%d\n", total);
for (int i = 1; i <= v[0]; ++i)
printf("%d ", v[i]);
return 0;
}