Pagini recente » Cod sursa (job #617274) | Cod sursa (job #2405088) | Cod sursa (job #1089026) | Cod sursa (job #3039577) | Cod sursa (job #500407)
Cod sursa(job #500407)
#include <string.h>
#include <cstdio>
using namespace std;
int F[1000];
int M, N;
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[200002];
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) {
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);
char pattern[2000001];
char text[2000001];
scanf("%s %s", &pattern, &text);
N = strlen(text); M = strlen(pattern);
kmp(text, pattern);
printf("%d\n", v[0]);
for (int i = 1; i <= v[0]; ++i)
printf("%d ", v[i]);
return 0;
}