Pagini recente » Cod sursa (job #1480321) | Cod sursa (job #1658081) | Cod sursa (job #2456598) | Cod sursa (job #596581) | Cod sursa (job #2215255)
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define NMAX 2000000
char P[NMAX + 1], T[NMAX + 1];
int pi[NMAX + 1], pos[1001];
int m, n, counter = 0;
void compute_prefix_function();
void kmp_match();
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", P);
scanf("%s", T);
m = strlen(P);
n = strlen(T);
compute_prefix_function();
kmp_match();
printf("%d\n", counter);
for (int i = 1; i <= min(counter, 1000); i++) {
printf("%d ", pos[i]);
}
printf("\n");
return 0;
}
void compute_prefix_function() {
pi[0] = -1;
int k = -1;
for (int q = 1; q < m; q++) {
while (k > -1 && P[k + 1] != P[q]) {
k = pi[k];
}
if (P[k + 1] == P[q]) {
k++;
}
pi[q] = k;
}
}
void kmp_match() {
int q = -1;
for (int i = 0; i < n; i++) {
while (q > -1 && P[q + 1] != T[i]) {
q = pi[q];
}
if (P[q + 1] == T[i]) {
q++;
}
if (q == m - 1) {
counter++;
if (counter <= 1000) {
pos[counter] = i - m + 1;
}
q = pi[q];
}
}
}