Pagini recente » Cod sursa (job #2356328) | Cod sursa (job #1419293) | Cod sursa (job #1588707) | Cod sursa (job #2615153) | Cod sursa (job #934753)
Cod sursa(job #934753)
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_N = 2000005;
int N, M, Z[MAX_N], MatchCount;
char Pattern[MAX_N], String[MAX_N];
vector<int> MatchPositions;
void BuildZ() {
Z[1] = 0;
for (int i = 2, p = 1, right = 1; i <= N; ++i) {
if (right >= i)
Z[i] = min(right - i + 1, Z[i - p + 1]);
for (; i + Z[i] <= N && Pattern[Z[i] + 1] == Pattern[i + Z[i]]; ++Z[i]);
if (i + Z[i] - 1 > right) {
p = i;
right = i + Z[i] - 1;;
}
}
}
void ZAlgorithm() {
BuildZ();
for (int i = 1, p = 0, right = 0; i <= M; ++i) {
int LCP = 0;
if (right >= i)
LCP = min(right - i + 1, Z[i - p + 1]);
for (; LCP < N && i + LCP <= M && Pattern[LCP + 1] == String[i + LCP]; ++LCP);
if (i + LCP - 1 > right) {
p = i;
right = i + LCP - 1;
}
if (LCP == N) {
++MatchCount;
if (MatchCount <= 1000)
MatchPositions.push_back(i - 1);
}
}
}
void Read() {
assert(freopen("strmatch.in", "r", stdin));
assert(scanf("%s\n%s", Pattern + 1, String + 1) == 2);
N = strlen(Pattern + 1);
M = strlen(String + 1);
}
void Print() {
assert(freopen("strmatch.out", "w", stdout));
printf("%d\n", MatchCount);
for (size_t i = 0; i < MatchPositions.size(); ++i)
printf("%d ", MatchPositions[i]);
printf("\n");
}
int main() {
Read();
ZAlgorithm();
Print();
return 0;
}