#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
vector<int> prefix_function(string &s) {
int n = s.size();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[j] != s[i]) j = pi[j - 1];
if (s[j] == s[i]) j++;
pi[i] = j;
}
return pi;
}
tuple<int, int, int> solve(string s, string t, bool f = false) {
int n = s.size(), m = t.size();
int a[n][m], b[n][m];
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
auto _s = s;
for (int i = 0; i < n; i++) {
string ss = s + '#' + t;
auto pi = prefix_function(ss);
for (int j = 0; j < m; j++) {
a[i][j] = pi[j + n - i + 1];
}
s.erase(s.begin());
}
s = _s;
for (int j = 0; j < m; j++) {
string ss = t + '#' + s;
auto pi = prefix_function(ss);
for (int i = 0; i < n; i++) {
b[i][j] = pi[i + m - j + 1];
}
t.erase(t.begin());
}
tuple<int, int, int> ret = {0, 0, 0};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ret = max(ret, {a[i][j], i, j - a[i][j] + 1});
ret = max(ret, {b[i][j], i - b[i][j] + 1, j});
if (i - 1 >= 0 && j + 1 < m) {
ret = max(ret, {a[i][j] + b[i - 1][j + 1], i - 1 - b[i - 1][j + 1] + 1, j - a[i][j] + 1});
}
}
}
if (f) {
auto &[l, i, j] = ret;
i = n - i - l;
}
return ret;
}
void testCase() {
string s, t;
cin >> s >> t;
auto a = solve(s, t);
reverse(s.begin(), s.end());
auto b = solve(s, t, true);
a = max(a, b);
auto [l, i, j] = a;
cout << l << "\n";
cout << i << " " << j << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
testCase();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
