Pagini recente » Cod sursa (job #2185798) | Cod sursa (job #1781563) | Cod sursa (job #2298528) | Cod sursa (job #2502885) | Cod sursa (job #1165825)
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_N = 4000005;
const int MAX_MATCHES = 1000;
int N, Z[MAX_N], M, MatchCount;
char String[MAX_N];
vector<int> Matches;
void BuildZ() {
Z[0] = 0;
for (int i = 1, p = 0, r = 0; i < N; ++i) {
if (r >= i)
Z[i] = min(r - i + 1, Z[p]);
else
Z[i] = 0;
for (; i + Z[i] < N && String[i + Z[i]] == String[Z[i]]; ++Z[i]);
}
}
void Solve() {
BuildZ();
for (int i = M + 1; i < N; ++i) {
if (Z[i] == M) {
++MatchCount;
if (int(Matches.size()) < MAX_MATCHES)
Matches.push_back(i - M - 1);
}
}
}
void Read() {
assert(freopen("strmatch.in", "r", stdin));
assert(scanf("%s", String) == 1);
M = strlen(String);
String[M] = '#';
assert(scanf("%s", String + M + 1) == 1);
N = strlen(String);
}
void Print() {
assert(freopen("strmatch.out", "w", stdout));
printf("%d\n", MatchCount);
for (int i = 0; i < int(Matches.size()); ++i)
printf("%d ", Matches[i]);
printf("\n");
}
int main() {
Read();
Solve();
Print();
return 0;
}