#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
const int maxn5 = 7e3 + 10;
int n, m;
string z;
vector <int> qu[maxn5];
int av[maxn5];
int l[maxn5], lp[maxn5], lcp[maxn5];
inline void find_lcp(){
int n = z.size();
fill(lcp, lcp + n, 0);
int l = 0, r = 0;
//cout << "alright " << z << endl;
for(int i = 1; i < n; i++){
if(i <= r)
lcp[i] = min(r - i + 1, lcp[i - l]);
//cout << i << ' ' << l << ' ' << r << ' ' << lcp[i] << endl;
while(i + lcp[i] < n && z[lcp[i]] == z[i + lcp[i]])
lcp[i]++;
if(i + lcp[i] - 1 > r){
l = i;
r = i + lcp[i] - 1;
}
//cout << i << ' ' << lcp[i] << endl;
}
return;
}
inline pair<int, pair<int, int>> solve(string s, string t){
//cout << "wow! " << endl;
n = s.size();
m = t.size();
string sp = s;
reverse(sp.begin(), sp.end());
int ans = 0, idt, ids;
for(int i = 0; i < m; i++){
z = "";
for(int j = i; j < m; j++)
z.pb(t[j]);
z = z + "$";
int id = z.size();
z = z + s;
find_lcp();
for(int j = 0; j < n; j++)
l[j] = lcp[j + id];
z = "";
for(int j = i - 1; j >= 0; j--)
z.pb(t[j]);
z = z + "$";
id = z.size();
z = z + sp;
find_lcp();
for(int j = 0; j < n; j++)
lp[j] = lcp[n - j - 1 + id];
int till = 0, till2 = 0;
for(int j = 0; j < n; j++){
//cout << i << ' ' << j << ' ' << l[j] << ' ' << lp[j] << endl;
qu[l[j] + j].pb(j);
av[max(0, j - lp[j] + 1)] = max(j, av[max(0, j - lp[j] + 1)]);
till = max(till, l[j] + j);
till2 = max(till2, max(0, j - lp[j] + 1));
}
int ind = 0, mx = -1;
for(int j = 0; j <= till; j++){
while(qu[j].size()){
int id = qu[j].back();
qu[j].pop_back();
while(ind <= till2 && ind <= j){
mx = max(mx, av[ind]);
av[ind] = -1;
ind++;
}
if(mx - id + 1 >= ans && mx - id + 1 >= 1){
ans = mx - id + 1;
ids = id;
if(j - id >= ans)
idt = i;
else
idt = i + j - id - 1 - (mx - id + 1) + 1;
}
}
}
}
return {ans, {ids, idt}};
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
string s, t; cin >> s >> t;
pair <int, pair<int, int>> ans1 = solve(s, t);
if(true){
reverse(t.begin(), t.end());
pair <int, pair<int, int>> ans2 = solve(s, t);
int len = ans2.fi, id = ans2.se.se;
id = int(t.size()) - id - 1;
id -= len - 1;
ans2.se.se = id;
if(ans1 < ans2)
ans1 = ans2;
}
cout << ans1.fi << '\n' << ans1.se.fi << ' ' << ans1.se.se << '\n';
}
Compilation message
necklace.cpp: In function 'std::pair<int, std::pair<int, int> > solve(std::string, std::string)':
necklace.cpp:102:25: warning: 'ids' may be used uninitialized in this function [-Wmaybe-uninitialized]
102 | return {ans, {ids, idt}};
| ^
necklace.cpp:102:25: warning: 'idt' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
568 ms |
708 KB |
Output is correct |
| 2 |
Correct |
557 ms |
720 KB |
Output is correct |
| 3 |
Correct |
607 ms |
828 KB |
Output is correct |
| 4 |
Correct |
483 ms |
704 KB |
Output is correct |
| 5 |
Correct |
497 ms |
688 KB |
Output is correct |
| 6 |
Correct |
539 ms |
824 KB |
Output is correct |
| 7 |
Correct |
554 ms |
708 KB |
Output is correct |
| 8 |
Correct |
546 ms |
800 KB |
Output is correct |
| 9 |
Correct |
551 ms |
708 KB |
Output is correct |
