Pagini recente » Monitorul de evaluare | Borderou de evaluare (job #3338961) | Cod sursa (job #3338970) | Cod sursa (job #205600) | Cod sursa (job #1614975)
#include <fstream>
#include <cstring>
using namespace std;
const int MAX_N = 2000000;
const int MAX_MATCH = 1000;
char A[2 * MAX_N + 2];
int Z[2 * MAX_N + 1];
int match[MAX_MATCH];
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.tie(0);
ios_base::sync_with_stdio(false);
int N, M;
int st, fn, matches;
fin >> A;
N = strlen(A);
A[N] = '$';
fin >> (A + N + 1);
N += (M = strlen(A + N + 1)) + 1;
st = 0, fn = 0;
for (int i = 1; i < N; ++ i) {
if (i <= fn) {
Z[i] = min(Z[i - st], fn - i + 1);
}
while (A[Z[i]] == A[i + Z[i]]) {
++ Z[i];
}
if (i + Z[i] - 1 > fn) {
st = i;
fn = i + Z[i] - 1;
}
}
matches = 0;
for (int i = N - M; i < N; ++ i) {
if (Z[i] == N - M - 1) {
if (matches < MAX_MATCH) {
match[matches] = i;
}
++ matches;
}
}
fout << matches << '\n'; matches = min(matches, MAX_MATCH);
for (int i = 0; i < matches; ++ i) {
fout << match[i] - N + M << " \n"[i == matches - 1];
}
fout.close();
return 0;
}