#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> prefixFunction(string& s) {
vector<int> pi(s.size());
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;
}
return pi;
}
string s, t;
void work(int& res, int& ls, int& lt, bool& o) {
if (o) {
reverse(s.begin(), s.end());
}
int n = s.size();
int m = t.size();
string g = s + "?" + t;
vector<vector<int>> pi(n);
for (int i = 0; i < n; i++) {
pi[i] = prefixFunction(g);
g.erase(g.begin());
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x = pi[i][n - i + 1 + j];
if (x > res) {
res = x;
ls = i;
lt = j - x + 1;
}
if (i + x < n && n - (i + x) + 1 + (j - x) < pi[i].size()) {
int y = pi[i + x][n - (i + x) + 1 + (j - x)];
if (x + y > res) {
res = x + y;
ls = (o ? n - (i + res - 1) - 1 : i);
lt = (j - x) - y + 1;
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> t;
bool o = 0;
int res = 0;
int ls = -1, lt = -1;
work(res, ls, lt, o);
o ^= 1;
work(res, ls, lt, o);
cout << res << '\n';
cout << ls << " " << lt << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |