#include <bits/stdc++.h>
// #include <iostream>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define sz(x) int((x).size())
#define all(a) begin(a), end(a)
#define pll pair<long long, long long>
#define vb vector<bool>
#define vll vector<long long>
#define vvll vector<vector<long long> >
#define vpl vector< pair<long long, long long> >
#define f(i,s,e) for(long long int i = s; i < e; i++)
#define cf(i,s,e) for(long long int i = s; i <= e; i++)
#define rf(i,s,e) for(long long int i = s; i >= e; i--)
#define print(a) for(auto x : a) cout << x << <<endl;
#define printp(a) for(auto x : a) cout << x.first << << x.second <<endl;
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
inline ll read() {ll x = 0, fh = 1; char ch = getchar(); while(!isdigit(ch)) {if (ch == '-') fh = -1; ch = getchar();} while (isdigit(ch)) {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();} return x*fh;}
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
ll t, n, m, k, a, b, tot;
string s1, s2;
ll lps[3009];
void solve() {
cin >> s1 >> s2;
f(i, 1, s1.size()) {
ll len = lps[i-1];
while (len && s1[len] != s1[i]) len = lps[len-1];
if (len == 0) {f(j, 0, i) if (s1[i] == s1[j]) len = j + 1;}
else if (s1[len] == s1[i]) len++;
lps[i] = len;
}
// f(i, 0, s1.size()) cout << lps[i] << " ";
// cout<<endl;
vector<vll> chars(27, vll());
f(i, 0, s1.size()) chars[s1[i] - 'a'].pb(i);
ll i1, i2, ans = 0;
f(i, 0, s2.size()) {
if (chars[s2[i] - 'a'].empty()) continue;
ll l = chars[s2[i] - 'a'].back();
ll j = i, r = l;
ll curr = 0;
while (j < s2.size() && r <= s1.size() && l >= 0) {
// cout << r << " " << j << endl;
if (r < s1.size() && s1[r] == s2[j]) {
j++; r++;
} else {
if (!chars[s2[j] - 'a'].empty()) {
ll back = lower_bound(all(chars[s2[j] - 'a']), l) - chars[s2[j] - 'a'].begin() - 1;
if (back != -1) {
ll temp = chars[s2[j] - 'a'][back];
ll start = temp, jj = j;
// cout << temp <<endl;
while (temp <= l && jj < s2.size()) {
if (temp == l && jj - i > ans) {
ans = jj - i;
i1 = start;
i2 = i;
}
if (temp != l && temp < s1.size() && s1[temp] == s2[jj]) {
temp++; jj++;
} else {
if (!temp) break;
do {
ll d = temp - start;
temp = lps[temp - 1];
start = temp - d;
} while (temp && s1[temp] != s2[jj]);
}
}
if (temp == l && jj - i > ans) {
ans = jj - i;
i1 = start;
i2 = i;
}
}
}
if (j - i > ans) {
ans = j - i;
i1 = l;
i2 = i;
}
do {
r = lps[r - 1];
} while (r && s1[r] != s2[j]);
l = r - (j - i);
}
}
if (j - i > ans) {
ans = j - i;
i1 = l;
i2 = i;
}
}
reverse(all(s2));
f(i, 0, s2.size()) {
if (chars[s2[i] - 'a'].empty()) continue;
ll l = chars[s2[i] - 'a'].back();
ll j = i, r = l;
ll curr = 0;
while (j < s2.size() && r <= s1.size() && l >= 0) {
if (r < s1.size() && s1[r] == s2[j]) {
j++; r++;
} else {
if (!chars[s2[j] - 'a'].empty()) {
ll back = lower_bound(all(chars[s2[j] - 'a']), l) - chars[s2[j] - 'a'].begin() - 1;
if (back != -1) {
ll temp = chars[s2[j] - 'a'][back];
ll start = temp, jj = j;
while (temp < l && jj < s2.size()) {
if (temp == l && jj - i > ans) {
ans = jj - i;
i1 = start;
i2 = s2.size() - jj;
}
if (temp != l && temp < s1.size() && s1[temp] == s2[jj]) {
temp++; jj++;
} else {
if (!temp) break;
do {
ll d = temp - start;
temp = lps[temp - 1];
start = temp - d;
} while (temp && s1[temp] != s2[jj]);
}
}
// cout << i << " " << l <<endl;
if (temp == l && jj - i > ans) {
ans = jj - i;
i1 = start;
i2 = s2.size() - jj;
}
}
}
if (j - i > ans) {
ans = j - i;
i1 = l;
i2 = s2.size() - j;
}
do {
r = lps[r - 1];
} while (r && s1[r] != s2[j]);
l = r - (j - i);
}
}
if (j - i > ans) {
ans = j - i;
i1 = l;
i2 = s2.size() - j;
}
}
cout << ans <<endl;
cout << i1 << " " << i2 <<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
t = 1;
while (t--) {
solve();
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
