#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
template <class T>
void setmin(T& lhs, const T& rhs) {
if (lhs > rhs) {
lhs = rhs;
}
}
template <class T>
void setmax(T& lhs, const T& rhs) {
if (lhs < rhs) {
lhs = rhs;
}
}
std::tuple<int, int, int> solve(const std::string& S, const std::string& T) {
const int N = (int) S.size();
const int M = (int) T.size();
Vec<Vec<int>> match(N + 1, Vec<int>(M + 1));
for (int i = N - 1; i >= 0; --i) {
for (int j = M - 1; j >= 0; --j) {
if (S[i] == T[j]) {
match[i][j] = match[i + 1][j + 1] + 1;
}
}
}
Vec<Vec<int>> min_j(N + 1, Vec<int>(M + 1, M + 1));
for (int i = 0; i <= N; ++i) {
for (int j = 0; j <= M; ++j) {
setmin(min_j[i][std::min(match[i][j] + j, M)], j);
}
for (int j = M; j > 0; --j) {
setmin(min_j[i][j - 1], min_j[i][j]);
}
}
std::tuple<int, int, int> ret(0, 0, 0);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
const auto len = match[i][j];
const auto j2 = min_j[i + len][j];
setmax(ret, std::make_tuple(len + (j - j2), i, j2));
}
}
return ret;
}
int main() {
std::string S, T;
std::cin >> S >> T;
const auto [a1, i1, j1] = solve(S, T);
std::reverse(T.begin(), T.end());
const auto [a2, i2, j2] = solve(S, T);
if (a1 >= a2) {
std::cout << a1 << '\n';
std::cout << i1 << ' ' << j1 << '\n';
}
else {
std::cout << a2 << '\n';
std::cout << i2 << ' ' << (((int) T.size() - j2 - 1) - a2 + 1) << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
5 ms |
1484 KB |
Output is correct |
7 |
Correct |
5 ms |
1484 KB |
Output is correct |
8 |
Correct |
5 ms |
1276 KB |
Output is correct |
9 |
Correct |
5 ms |
1484 KB |
Output is correct |
10 |
Correct |
5 ms |
1500 KB |
Output is correct |
11 |
Correct |
5 ms |
1504 KB |
Output is correct |
12 |
Correct |
5 ms |
1448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
5 ms |
1484 KB |
Output is correct |
7 |
Correct |
5 ms |
1484 KB |
Output is correct |
8 |
Correct |
5 ms |
1276 KB |
Output is correct |
9 |
Correct |
5 ms |
1484 KB |
Output is correct |
10 |
Correct |
5 ms |
1500 KB |
Output is correct |
11 |
Correct |
5 ms |
1504 KB |
Output is correct |
12 |
Correct |
5 ms |
1448 KB |
Output is correct |
13 |
Correct |
281 ms |
71012 KB |
Output is correct |
14 |
Correct |
241 ms |
71008 KB |
Output is correct |
15 |
Correct |
268 ms |
66908 KB |
Output is correct |
16 |
Correct |
248 ms |
69932 KB |
Output is correct |
17 |
Correct |
250 ms |
68484 KB |
Output is correct |
18 |
Correct |
263 ms |
70464 KB |
Output is correct |
19 |
Correct |
258 ms |
70344 KB |
Output is correct |
20 |
Correct |
261 ms |
68404 KB |
Output is correct |
21 |
Correct |
262 ms |
69056 KB |
Output is correct |