#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100 + 10;
const int base = 37;
const int mod = 1e9 + 7;
int n;
string s;
ll sa[maxn], pos[maxn], pw[maxn], hsh[maxn], rev[maxn], answer;
vector<int> seg[4 * maxn];
int get_rev(int L, int R){
ll ret = rev[L] - rev[R + 1] * pw[R - L + 1] % mod;
if (ret < 0)
ret += mod;
return ret;
}
int get_hsh(int L, int R){
if (L == 0)
return hsh[R];
ll ret = hsh[R] - hsh[L - 1] * pw[R - L + 1] % mod;
if (ret < 0)
ret += mod;
return ret;
}
int lcp(int fi, int se){
int lo = 0, hi = min(n - fi + 1, n - se + 1);
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (get_hsh(fi, fi + mid - 1) == get_hsh(se, se + mid - 1))
lo = mid;
else
hi = mid;
}
return lo;
}
bool cmp(int fi, int se){
int lo = 0, hi = min(n - fi + 1, n - se + 1);
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (get_hsh(fi, fi + mid - 1) == get_hsh(se, se + mid - 1))
lo = mid;
else
hi = mid;
}
if (lo == n - fi or (lo < n - se and s[fi + lo] < s[se + lo]))
return 1;
return 0;
}
void buildSA(){
for (int i = 0; i < n; i++)
sa[i] = i;
sort(sa, sa + n, cmp);
for (int i = 0; i < n; i++)
pos[sa[i]] = i;
}
void check(int L, int R){
int len = R - L + 1;
int fi, se;
int lo = -1, hi = pos[L];
// cout << "checking : " << lo << " " << hi << endl;
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (lcp(L, sa[mid]) >= len)
hi = mid;
else
lo = mid;
}
fi = hi;
lo = pos[L], hi = n;
// cout << "checking : " << lo << " " << hi << endl;
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (lcp(L, sa[mid]) >= len)
lo = mid;
else
hi = mid;
}
se = lo;
// cout << "then is : " << fi << " " << se << endl;
answer = max(answer, 1ll * len * (se - fi + 1));
}
void get(int id, int L, int R, int idx, int len){
for (int i = 0; i < seg[id].size() and seg[id][i] < 0; i++){
int t = -seg[id][i];
t --;
t = (t - idx + 1);
if (2 * t <= len)
break;
// cout << "this is palindrome : " << idx << " " << idx + 2 * t - 1 << endl;
check(idx, idx + 2 * t - 1);
}
for (int i = (int)(seg[id].size()) - 1; i >= 0 and seg[id][i] > 0; i--){
int t = seg[id][i];
t --;
t = (t - idx);
if (2 * t + 1 <= len)
break;
// cout << "this is palindrome : " << idx << " " << idx + 2 * t << endl;
check(idx, idx + 2 * t);
}
if (L + 1 == R)
return;
int mid = (L + R) >> 1;
if (idx < mid)
get(2 * id + 0, L, mid, idx, len);
else
get(2 * id + 1, mid, R, idx, len);
}
void add(int id, int L, int R, int l, int r, int x){
if (L == l and R == r){
seg[id].push_back(x);
return;
}
int mid = (L + R) >> 1;
if (l < mid)
add(2 * id + 0, L, mid, l, min(mid, r), x);
if (mid < r)
add(2 * id + 1, mid, R, max(l, mid), r, x);
}
int main(){
ios_base::sync_with_stdio(false);
cin >> s;
n = s.size();
pw[0] = 1;
for (int i = 1; i <= n; i++)
pw[i] = pw[i - 1] * base % mod;
for (int i = 0; i < n; i++){
if (i == 0)
hsh[i] = (int)(s[i] - 'a' + 1);
else
hsh[i] = (hsh[i - 1] * base + (int)(s[i] - 'a' + 1)) % mod;
}
for (int i = n - 1; i >= 0; i--)
rev[i] = (rev[i + 1] * base + (int)(s[i] - 'a' + 1)) % mod;
buildSA();
for (int i = 0; i < n; i++){
int lo = 0, hi = min(i, n - i - 1) + 1;
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (get_hsh(i - mid, i - 1) == get_rev(i + 1, i + mid))
lo = mid;
else
hi = mid;
}
add(1, 0, n, i - lo, i + 1, i + 1);
if (i < n - 1){
lo = 0, hi = min(i + 2, n - i);
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (get_hsh(i - mid + 1, i) == get_rev(i + 1, i + mid))
lo = mid;
else
hi = mid;
}
if (lo > 0)
add(1, 0, n, i - lo + 1, i + 1, -(i+1));
}
}
for (int i = 1; i < 4 * maxn; i++)
sort(seg[i].begin(), seg[i].end());
for (int i = 0; i < n; i++){
int idx = sa[i];
int len = 0;
if (i > 0)
len = lcp(sa[i], sa[i - 1]);
get(1, 0, n, idx, len);
}
cout << answer << endl;
}
Compilation message
palindrome.cpp: In function 'void get(int, int, int, int, int)':
palindrome.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < seg[id].size() and seg[id][i] < 0; i++){
~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
384 KB |
Output is correct |
15 |
Correct |
3 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
3 ms |
384 KB |
Output is correct |
19 |
Correct |
3 ms |
384 KB |
Output is correct |
20 |
Correct |
3 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
380 KB |
Output is correct |
22 |
Correct |
3 ms |
384 KB |
Output is correct |
23 |
Correct |
3 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
3 ms |
384 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
4 ms |
384 KB |
Output is correct |
28 |
Correct |
3 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
3 ms |
384 KB |
Output is correct |
31 |
Correct |
3 ms |
384 KB |
Output is correct |
32 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4 ms |
1024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
1544 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |