#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const int MAXN = (int) 3e5;
const int B = 41;
const int LOG = 19;
char str[MAXN + 1];
struct Data {
int val1, val2;
int pos;
bool operator <(const Data &other) const {
if(val1 == other.val1)
return val2 < other.val2;
return val1 < other.val1;
}
}aux[MAXN + 1];
int P[MAXN + 1][LOG + 1], fr[26], lg;
int rmq[MAXN + 1][LOG + 1];
int ord[MAXN + 1], where[MAXN + 1];
char Log[MAXN + 1];
bool cmp(int a, int b) {
return P[a][lg] < P[b][lg];
}
inline void suffix_array(int n) {
int i;
for(i = 1; i <= n; i++) {
fr[str[i] - 'a']++;
}
for(i = 1; i < 26; i++) {
fr[i] += fr[i - 1];
}
for(i = 1; i <= n; i++) {
P[i][0] = fr[str[i] - 'a'];
}
for(lg = 1; (1 << lg) <= 2 * n; lg++) {
for(i = 1; i <= n; i++) {
if(i + (1 << (lg - 1)) <= n) {
aux[i] = {P[i][lg - 1], P[i + (1 << (lg - 1))][lg - 1], i};
}
else {
aux[i] = {P[i][lg - 1], 0, i};
}
}
sort(aux + 1, aux + n + 1);
int cur = 0;
for(i = 1; i <= n; i++) {
if(aux[i].val1 != aux[i - 1].val1 || aux[i].val2 != aux[i - 1].val2) {
cur++;
}
P[aux[i].pos][lg] = cur;
}
}
lg--;
for(i = 1; i <= n; i++) {
ord[i] = i;
}
sort(ord + 1, ord + n + 1, cmp);
for(i = 1; i <= n; i++) {
where[ord[i]] = i;
}
for(i = 1; i < n; i++) {
int a = ord[i], b = ord[i + 1];
for(int bit = lg; bit >= 0; bit--) {
if(a + (1 << bit) <= n + 1 && b + (1 << bit) <= n + 1 && P[a][bit] == P[b][bit]) {
a += (1 << bit);
b += (1 << bit);
}
}
rmq[i][0] = a - ord[i];
}
for(i = 2; i <= n; i++) {
Log[i] = Log[i >> 1] + 1;
}
for(int bit = 1; bit < lg; bit++) {
for(i = 1; i + (1 << bit) <= n + 1; i++) {
rmq[i][bit] = min(rmq[i][bit - 1], rmq[i + (1 << (bit - 1))][bit - 1]);
}
}
}
inline int get(int l, int r) {
int bit = Log[r - l + 1];
return min(rmq[l][bit], rmq[r - (1 << bit) + 1][bit]);
}
inline int solve(int pos, int len, int n) {
int res1 = pos;
for(int step = 1 << 18; step; step >>= 1) {
if(res1 - step > 0 && get(res1 - step, pos - 1) >= len) {
res1 -= step;
}
}
int res2 = pos;
for(int step = 1 << 18; step; step >>= 1) {
if(res2 + step <= n && get(pos, res2 + step) >= len) {
res2 += step;
}
}
return res2 - res1 + 1;
}
ull pw[MAXN + 1], hsh[MAXN + 1];
inline ull get_hsh(int l, int r) {
return hsh[r] - hsh[l - 1] * pw[r - l + 1];
}
int len[2 * MAXN + 5];
inline void manacher(int n) {
vector <char> aux(2 * n + 5);
int i, sz = 0;
for(i = 1; i <= n; i++) {
aux[++sz] = '*';
aux[++sz] = str[i];
}
aux[++sz] = '*';
int p = 0;
for(i = 1; i <= sz; i++) {
if(p + len[p] >= i) {
len[i] = min(len[2 * p - i], p + len[p] - i);
}
while(i - len[i] > 0 && i + len[i] <= sz && aux[i - len[i]] == aux[i + len[i]]) {
len[i]++;
}
if(i + len[i] > p + len[p]) {
p = i;
}
}
}
map <ull, bool> mp;
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i;
ios::sync_with_stdio(false);
cin >> str + 1;
int n = strlen(str + 1);
suffix_array(n);
manacher(n);
pw[0] = 1;
for(i = 1; i <= n; i++) {
pw[i] = pw[i - 1] * B;
hsh[i] = hsh[i - 1] * B + str[i] - 'a' + 1;
}
ll ans = 0;
for(i = 2; i <= 2 * n; i++) {
//cerr << i << " " << len[i] << "\n";
if(i % 2 == 0) {
for(int j = len[i] / 2; j >= 1; j--) {
ull cur = get_hsh(i / 2 - j + 1, i / 2 + j - 1);
if(mp[cur] == 0) {
mp[cur] = 1;
ans = max(ans, 1LL * solve(where[i / 2 - j + 1], (2 * j - 1), n) * (2 * j - 1));
}
else {
break;
}
}
}
else {
for(int j = len[i] / 2; j >= 1; j--) {
ull cur = get_hsh(i / 2 - j + 1, i / 2 + j);
if(mp[cur] == 0) {
//cerr << i / 2 - j + 1 << " " << i / 2 + j << "\n";
mp[cur] = 1;
ans = max(ans, 1LL * solve(where[i / 2 - j + 1], 2 * j, n) * 2 * j);
}
else {
break;
}
}
}
}
cout << ans;
//cin.close();
//cout.close();
return 0;
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:150:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
cin >> str + 1;
~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
524 KB |
Output is correct |
3 |
Correct |
2 ms |
524 KB |
Output is correct |
4 |
Correct |
2 ms |
524 KB |
Output is correct |
5 |
Correct |
2 ms |
544 KB |
Output is correct |
6 |
Correct |
2 ms |
544 KB |
Output is correct |
7 |
Correct |
2 ms |
544 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
588 KB |
Output is correct |
10 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
836 KB |
Output is correct |
2 |
Correct |
3 ms |
836 KB |
Output is correct |
3 |
Correct |
3 ms |
968 KB |
Output is correct |
4 |
Correct |
3 ms |
968 KB |
Output is correct |
5 |
Correct |
3 ms |
1064 KB |
Output is correct |
6 |
Correct |
3 ms |
1064 KB |
Output is correct |
7 |
Correct |
4 ms |
1064 KB |
Output is correct |
8 |
Correct |
3 ms |
1064 KB |
Output is correct |
9 |
Correct |
3 ms |
1064 KB |
Output is correct |
10 |
Incorrect |
3 ms |
1064 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
3428 KB |
Output is correct |
2 |
Incorrect |
19 ms |
3428 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
291 ms |
27328 KB |
Output is correct |
2 |
Correct |
259 ms |
27388 KB |
Output is correct |
3 |
Correct |
253 ms |
27444 KB |
Output is correct |
4 |
Incorrect |
331 ms |
27620 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1093 ms |
80508 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |