Pagini recente » Cod sursa (job #3004554) | Cod sursa (job #1707886) | Cod sursa (job #281294) | Cod sursa (job #2607413) | Cod sursa (job #1423663)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int MX = 2*1e6+1;
int n, m, F[MX];
char S[MX], P[MX];
vector<int> pos;
void build() {
F[0] = 0, F[1] = 0;
for (int i = 2; i <= m; i++) {
int j = F[i-1];
while (1) {
if (P[j] == P[i-1]) {
F[i] = j+1;
break;
}
else if (j > 0) {
j = F[j];
}
else {
F[i] = 0;
break;
}
}
}
}
void kmp() {
int i = 0, j = 0;
while (1) {
if (i == n) break;
if (P[j] == S[i]) {
i++, j++;
if (j == m) {
pos.push_back(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", &P, &S);
n = strlen(S), m = strlen(P);
build();
kmp();
int sz = pos.size();
printf("%d\n", min(sz, 1000));
for (int i = 0; i < min(sz, 1000); i++) {
printf("%d ", pos[i]);
}
return 0;
}