#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 = 4e3 + 10;
int n, m;
//int mod[2] = {1000000007, 1000000009};
ll base[2] = {37, 31};
ll pw[2][maxn5];
ll has[4][2][maxn5];
vector <pair<int, int>> av, qu;
inline ll get_hash(int ty, int id, int l, int r){
if(l == 0)
return has[ty][id][r];
return (has[ty][id][r] - has[ty][id][l - 1] * pw[id][r - l + 1]);
}
inline int get_lim(int ty, int l){
if(ty == 0 || ty == 2)
return n - l;
return m - l;
}
inline bool same(int ty1, int l1, int ty2, int l2, int len){
//cout << ty1 << ' ' << l1 + len - 1 << ' ' << ty2 << ' ' << l2 + len - 1 << endl;
/*
if(ty1 == 0 && l1 + len - 1 >= n)
return false;
if(ty1 == 1 && l1 + len - 1 >= m)
return false;
if(ty1 == 2 && l1 + len - 1 >= n)
return false;
if(ty1 == 3 && l1 + len - 1 >= m)
return false;
if(ty2 == 0 && l2 + len - 1 >= n)
return false;
if(ty2 == 1 && l2 + len - 1 >= m)
return false;
if(ty2 == 2 && l2 + len - 1 >= n)
return false;
if(ty2 == 3 && l2 + len - 1 >= m)
return false;
//*/
if(get_hash(ty1, 0, l1, l1 + len - 1) != get_hash(ty2, 0, l2, l2 + len - 1))
return false;
/*
if(get_hash(ty1, 1, l1, l1 + len - 1) != get_hash(ty2, 1, l2, l2 + len - 1))
return false;
*/
return true;
}
inline int lcp(int ty1, int id1, int ty2, int id2){
int l = 0, r = min(get_lim(ty1, id1), get_lim(ty2, id2)) + 1;
//cout << "here " << ty1 << ' ' << id1 << ' ' << ty2 << ' ' << id2 << ' ' << r << endl;
while(r - l > 1){
int mid = (l + r) >> 1;
if(same(ty1, id1, ty2, id2, mid))
l = mid;
else
r = mid;
}
return l;
}
inline pair<int, pair<int, int>> solve(string s, string t){
//cout << "wow! " << endl;
n = s.size();
m = t.size();
string sp = s, tp = t;
reverse(sp.begin(), sp.end());
reverse(tp.begin(), tp.end());
for(int j = 0; j < 1; j++){
pw[j][0] = 1;
for(int i = 1; i < maxn5; i++)
pw[j][i] = pw[j][i - 1] * base[j];
ll cur = 0;
for(int i = 0; i < n; i++){
cur = (cur * base[j] + s[i] - 'a' + 1);
has[0][j][i] = cur;
}
cur = 0;
for(int i = 0; i < m; i++){
cur = (cur * base[j] + t[i] - 'a' + 1);
has[1][j][i] = cur;
}
cur = 0;
for(int i = 0; i < n; i++){
cur = (cur * base[j] + sp[i] - 'a' + 1);
has[2][j][i] = cur;
}
cur = 0;
for(int i = 0; i < m; i++){
cur = (cur * base[j] + tp[i] - 'a' + 1);
has[3][j][i] = cur;
}
}
int ans = 0, idt, ids;
for(int i = 0; i < m; i++){
qu.clear();
av.clear();
for(int j = 0; j < n; j++){
int l = lcp(1, i, 0, j);
qu.pb({l + j, j});
//cout << i << ' ' << j << ' ' << l << '\n';
l = i == 0 ? 0 : lcp(3, m - i, 2, n - j - 1);
av.pb({j - l + 1, j});
//cout << i << ' ' << j << ' ' << l << '\n';
}
sort(all(qu));
sort(all(av));
int ind = 0, mx = -1;
for(auto [val, id] : qu){
while(ind < av.size() && av[ind].fi <= val){
mx = max(mx, av[ind].se);
ind++;
}
if(mx - id + 1 >= ans && mx - id + 1 >= 1){
ans = mx - id + 1;
ids = id;
if(val - id >= ans)
idt = i;
else
idt = i + val - 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(s.size() <= 500){
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:133:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | while(ind < av.size() && av[ind].fi <= val){
| ~~~~^~~~~~~~~~~
necklace.cpp:148:25: warning: 'ids' may be used uninitialized in this function [-Wmaybe-uninitialized]
148 | return {ans, {ids, idt}};
| ^
necklace.cpp:148:25: warning: 'idt' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Correct |
40 ms |
380 KB |
Output is correct |
| 7 |
Correct |
40 ms |
332 KB |
Output is correct |
| 8 |
Correct |
30 ms |
332 KB |
Output is correct |
| 9 |
Correct |
39 ms |
332 KB |
Output is correct |
| 10 |
Correct |
32 ms |
332 KB |
Output is correct |
| 11 |
Correct |
31 ms |
332 KB |
Output is correct |
| 12 |
Correct |
31 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Correct |
40 ms |
380 KB |
Output is correct |
| 7 |
Correct |
40 ms |
332 KB |
Output is correct |
| 8 |
Correct |
30 ms |
332 KB |
Output is correct |
| 9 |
Correct |
39 ms |
332 KB |
Output is correct |
| 10 |
Correct |
32 ms |
332 KB |
Output is correct |
| 11 |
Correct |
31 ms |
332 KB |
Output is correct |
| 12 |
Correct |
31 ms |
332 KB |
Output is correct |
| 13 |
Partially correct |
1313 ms |
540 KB |
Output is partially correct |
| 14 |
Partially correct |
1474 ms |
544 KB |
Output is partially correct |
| 15 |
Correct |
1290 ms |
560 KB |
Output is correct |
| 16 |
Partially correct |
1488 ms |
548 KB |
Output is partially correct |
| 17 |
Incorrect |
1176 ms |
552 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
