#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast,unroll-loops")
#define ll long long
#define all(x) x.begin(), x.end()
using namespace std;
using namespace __gnu_pbds;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
int n;
string s;
vector<ll> h;
vector<ll> p;
vector<int> d1;
vector<int> d2;
vector<int> arr;
void calc(){
h.resize(n + 1);
p.resize(n + 1, 1);
for(int i = 1; i < n; i++){
p[i] *= p[i - 1];
p[i] %= INF;
}
for(int i = 0; i < n; i++){
if(i) h[i] += h[i - 1];
h[i] += (s[i] - 'a' + 1) * p[i];
h[i] %= INF;
}
}
void man(){
d1.resize(n, 0);
d2.resize(n, 0);
int l = 0, r = -1;
for(int i = 0; i < n; i++){
int k = i > r ? 1 : min(d1[l + r - i], r - i + 1);
while(i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
d1[i] = k;
if(i + k - 1 > r){
r = i + k - 1;
l = i - k + 1;
}
}
l = 0, r = -1;
for(int i = 0; i < n; i++){
int k = i > r ? 0 : min(d2[l + r - i + 1], r - i + 1);
while(i - k - 1 >= 0 && i + k < n && s[i + k] == s[i - k - 1]) k++;
d2[i] = k;
if(i + k - 1 > r){
l = i - k, r = i + k - 1;
}
}
}
void sufmas(){
arr.resize(n + 1);
vector<int> c(n + 1, 0);
vector<int> c1(n + 1);
vector<int> arr1(n + 1);
s += '#';
map<int, vector<int> > cnt;
for(int i = 0; i <= n; i++){
cnt[s[i] - 'a'].push_back(i);
}
int sch = 0;
int sch1 = 0;
for(auto i: cnt){
for(auto j: i.second){
arr[sch] = j;
c[j] = sch1;
sch++;
}
if(i.second.size()) sch1++;
}
cnt.clear();
vector<vector<int> > q(n + 1);
for(int k = 0; k < 19; k++){
for(int i = 0; i <= n; i++){
//cout << (arr[i] + (1 << k)) % (n + 1) << " " << c[(arr[i] + (1 << k)) % (n + 1)] << endl;
q[c[(arr[i] + (1 << k)) % (n + 1)]].push_back(arr[i]);
}
sch = 0;
for(int i = 0; i <= n; i++){
for(auto j: q[i]){
arr1[sch] = j;
sch++;
}
q[i].clear();
}
arr.swap(arr1);
for(int i = 0; i <= n; i++){
q[c[arr[i]]].push_back(arr[i]);
}
sch = 0;
for(int i = 0; i <= n; i++){
for(auto j: q[i]){
arr1[sch] = j;
sch++;
}
q[i].clear();
}
arr.swap(arr1);
c1[arr[0]] = 0;
sch = 0;
int a1, a2, b1, b2;
for(int i = 1; i <= n; i++){
a1 = c[arr[i]];
a2 = c[arr[i - 1]];
b1 = c[(arr[i] + (1 << k)) % (n + 1)];
b2 = c[(arr[i - 1] + (1 << k)) % (n + 1)];
if(a1 != a2 || b1 != b2) sch++;
c1[arr[i]] = sch;
}
c.swap(c1);
}
}
bool cmp(int a, int b, int cnt){
if(a + cnt > n || b + cnt > n) return 0;
ll h1 = h[a + cnt - 1];
ll h2 = h[b + cnt - 1];
if(a) h1 = (h1 - h[a - 1] + INF) % INF;
if(b) h2 = (h2 - h[b - 1] + INF) % INF;
if(b > a) h1 = (h1 * 1LL * p[b - a]) % INF;
if(a > b) h2 = (h2 * 1LL * p[a - b]) % INF;
return h1 == h2;
}
int bin_search(int pos, int cnt){
if(cnt == 0) return 0;
int l = 1, r = pos;
int l1 = 0, r1 = 0;
while(l <= r){
int mid = (l + r) / 2;
if(cmp(arr[mid], arr[pos], cnt)){
l1 = mid;
r = mid - 1;
}
else l = mid + 1;
}
l = pos, r = n;
while(l <= r){
int mid = (l + r) / 2;
if(cmp(arr[mid], arr[pos], cnt)){
r1 = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
}
return r1 - l1 + 1;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//ifstream cin("input.txt");
//ofstream cout("output.txt");
cin >> s;
n = s.size();
calc();
man();
sufmas();
vector<int> c(n + 1, 0);
for(int i = 1; i <= n; i++){
c[arr[i]] = i;
}
/*for(int i = 1; i <= n; i++){
cout << arr[i] << " ";
}
cout << endl;*/
ll ans = 0;
for(int i = 0; i < n; i++){
// cout << i << " " << d1[i] << " " << d2[i] << " " << c[i - d1[i] + 1] << " " << c[i - d2[i]] << " ----> " << bin_search(c[i - d1[i] + 1], d1[i] * 2 - 1) << " " << bin_search(c[i - d2[i]], d2[i] * 2) << endl;
ans = max(ans, (d1[i] * 2 - 1) * 1LL * bin_search(c[i - d1[i] + 1], d1[i] * 2 - 1));
ans = max(ans, (d2[i] * 2) * 1LL * bin_search(c[i - d2[i]], d2[i] * 2));
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1880 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1880 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1620 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1628 KB |
Output is correct |
| 8 |
Incorrect |
11 ms |
1368 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
15680 KB |
Output is correct |
| 2 |
Correct |
61 ms |
14524 KB |
Output is correct |
| 3 |
Correct |
71 ms |
16072 KB |
Output is correct |
| 4 |
Correct |
88 ms |
15644 KB |
Output is correct |
| 5 |
Incorrect |
145 ms |
14276 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
38512 KB |
Output is correct |
| 2 |
Correct |
217 ms |
46524 KB |
Output is correct |
| 3 |
Correct |
207 ms |
61808 KB |
Output is correct |
| 4 |
Incorrect |
274 ms |
44228 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
