Pagini recente » Cod sursa (job #2718145) | Cod sursa (job #1123730) | Cod sursa (job #1465310) | Cod sursa (job #1298669) | Cod sursa (job #1165830)
#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[i - p]);
else
Z[i] = 0;
for (; i + Z[i] < N && String[i + Z[i]] == String[Z[i]]; ++Z[i]);
if (i + Z[i] - 1 > r) {
p = i;
r = i + Z[i] - 1;
}
}
}
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));
gets(String);
M = strlen(String);
String[M] = '#';
gets(String + M + 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;
}