#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <climits>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <list>
#include <random>
#include <initializer_list>
#include <chrono>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
vector<int> pi1(6002), pi2(6002);
void work(string& s, vector<int>& pi) {
for (int i = 1; i < s.size(); i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) {
j = pi[j - 1];
}
if (s[i] == s[j]) {
j++;
}
pi[i] = j;
}
}
string R1, R2, T1;
tuple<int, int, int> solve(string s, string t, bool r) {
int n = s.size();
int m = t.size();
T1 = t;
reverse(T1.begin(), T1.end());
R1 = "?" + T1;
R2 = s + "?" + t;
int res = 0;
int a = -1, b = -1;
for (int i = 0; i < n; i++) {
R1.insert(R1.begin(), s[i]);
R2.erase(R2.begin());
work(R1, pi1);
work(R2, pi2);
for (int j = -1; j < m; j++) {
int x = pi1[i + m - j];
int y = pi2[n - i + j];
if (x + y > res) {
res = x + y;
a = (r ? n - (i + y) - 1 : i - x + 1);
b = j - y + 1;
}
}
}
return {res, a, b};
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string s, t;
cin >> s >> t;
T1 = t;
reverse(T1.begin(), T1.end());
tuple<int, int, int> ans = solve(s, t, 0);
reverse(s.begin(), s.end());
ans = std::max(ans, solve(s, t, 1));
cout << get<0>(ans) << '\n';
cout << get<1>(ans) << " " << get<2>(ans) << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |