// time-limit: 3000
/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define nl "\n"
// #define debug(text) if(do_debug) {cout << (#text) << ": " << text << endl;}
#ifdef naman1601
#define debug(text) cout << (#text) << ": " << text << endl;
#else
#define debug(text)
#endif
const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;
void kmp(vector<int>& v, int len, string s) {
fr(i, 1, len) {
int j = v[i - 1];
while(j > 0 && s[i] != s[j]) {
j = v[j - 1];
}
if(s[i] == s[j]) {
j++;
}
v[i] = j;
}
}
string s, t;
int sl, tl;
int ans = 0;
pii ap = make_pair(-1, -1);
void f() {
fr(i, 1, sl + 1) {
string first_half = s.substr(0, i);
string second_half = s.substr(i, s.length() - i);
string t_prime = t;
reverse(first_half.begin(), first_half.end());
reverse(t_prime.begin(), t_prime.end());
string aux = second_half + t;
string aux_prime = first_half + t_prime;
int auxl = aux.length();
int aux_primel = aux_prime.length();
vector<int> pf(auxl, 0), pf_prime(aux_primel, 0);
kmp(pf, auxl, aux);
kmp(pf_prime, aux_primel, aux_prime);
fr(j, 1, tl + 1) {
int temp = pf[second_half.length() + j] + pf_prime[first_half.length() + t.length() - (j + 1) - 1];
if(temp > ans) {
ans = temp;
ap = make_pair(i - pf_prime[first_half.length() + t.length() - (j + 1) - 1], j - pf[second_half.length() + j] + 1);
}
}
}
}
void g() {
fr(i, 1, sl + 1) {
string first_half = s.substr(0, i);
string second_half = s.substr(i, s.length() - i);
string t_prime = t;
reverse(first_half.begin(), first_half.end());
reverse(t_prime.begin(), t_prime.end());
string aux = second_half + t;
string aux_prime = first_half + t_prime;
int auxl = aux.length();
int aux_primel = aux_prime.length();
vector<int> pf(auxl, 0), pf_prime(aux_primel, 0);
kmp(pf, auxl, aux);
kmp(pf_prime, aux_primel, aux_prime);
fr(j, 1, tl + 1) {
int temp = pf[second_half.length() + j] + pf_prime[first_half.length() + t.length() - (j + 1) - 1];
if(temp > ans) {
ans = temp;
ap = make_pair(s.length() - (i + pf[second_half.length() + j] - 1) - 1, j - pf[second_half.length() + j] + 1);
}
}
}
}
void solve() {
cin >> s >> t;
sl = s.length();
tl = t.length();
s = "(" + s + ")";
t = "[" + t + "]";
f();
reverse(s.begin(), s.end());
g();
cout << ans << "\n" << ap.fe - 1 << " " << ap.se - 1 << nl;
}
int main() {
speed;
int q = 1;
// cin >> q;
while(q-- > 0) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
351 ms |
520 KB |
Output is correct |
| 2 |
Correct |
286 ms |
448 KB |
Output is correct |
| 3 |
Correct |
374 ms |
440 KB |
Output is correct |
| 4 |
Correct |
279 ms |
440 KB |
Output is correct |
| 5 |
Correct |
222 ms |
332 KB |
Output is correct |
| 6 |
Correct |
244 ms |
452 KB |
Output is correct |
| 7 |
Correct |
280 ms |
452 KB |
Output is correct |
| 8 |
Correct |
295 ms |
332 KB |
Output is correct |
| 9 |
Correct |
312 ms |
392 KB |
Output is correct |
