This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
using i64 = long long;
template <class T>
using vec = vector<T>;
template <class T>
istream& operator>>(istream& is, vec<T>& V) {
for (auto& x : V) is >> x;
return is;
}
mt19937_64 rng((uint64_t)time(0));
constexpr int kN = 3'000;
using Hs = uint64_t;
Hs hs[2][kN + 2], pw[kN + 1];
void solve() {
auto st = clock();
string S, T; cin >> S >> T;
int n = size(S);
int m = size(T);
bool fl = false;
if (n < m)
swap(n, m), swap(S, T), fl = true;
Hs bs{};
for (auto x = rng(); (bs = x, x) % 2 == 0; )
x = rng();
pw[0] = 1;
for (int i = 0; i < m; i++) {
pw[i + 1] = pw[i] * bs;
hs[0][i + 1] = hs[0][i] * bs + T[i];
}
for (int i = m - 1; i >= 0; i--) {
hs[1][i] = hs[1][i + 1] * bs + T[i];
}
auto get_0 = [&](int l, int r) -> Hs {
return hs[0][r] - hs[0][l] * pw[r - l];
};
auto get_1 = [&](int l, int r) -> Hs {
return hs[1][l] - hs[1][r] * pw[r - l];
};
map<Hs, int> mp;
for (int i = 0; i < n; i++) {
Hs h{};
for (int j = i; j < n; j++) {
h = h * bs + S[j];
mp[h] = i;
}
}
vec<int> id(m);
iota(ALL(id), 0);
shuffle(ALL(id), rng);
int len{};
pair<int, int> ans{};
for (int t = 0; t < m; t++) {
if (clock() - st >= 1.47 * CLOCKS_PER_SEC)
break;
for (int i = m - 1; i >= id[t]; i--) {
if (i - id[t] + 1 <= len) break;
Hs h = get_0(id[t], i + 1);
Hs r = get_1(id[t], i + 1);
bool f = false;
Hs p = pw[i - id[t]];
for (int j = id[t]; j <= i; j++) {
if (i - id[t] + 1 > len) {
auto it = mp.find(h);
if (it != end(mp)) {
len = i - id[t] + 1, ans = {it->second, id[t]};
f = true;
break;
}
}
h -= p * T[j];
h *= bs;
h += T[j];
}
if (f) break;
for (int j = i; j >= id[t]; j--) {
if (i - id[t] + 1 > len) {
auto it = mp.find(r);
if (it != end(mp)) {
len = i - id[t] + 1, ans = {it->second, id[t]};
f = true;
break;
}
}
r -= p * T[j];
r *= bs;
r += T[j];
}
if (f) break;
}
}
if (fl)
swap(ans.first, ans.second);
cout << len << '\n';
cout << ans.first << ' ' << ans.second << '\n';
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |