• 2018-01-07
• 0
• 0

# Problem:

Time Limit: 10 Sec  Memory Limit: 128 MB

## Description

x 的子串是指在 x 中连续的一段字符所组成的字符串。例如 bc 是 abcd 的子串，而 ac 不是。
x 的回文子串，就是指满足回文性质的 x 的子串。
x 的双倍回文子串，就是指满足双倍回文性质的 x 的子串。

16
ggabaabaabaaball

12

N<=500000

SHOI 2011

# Solution:

• Y - pal[Y] ≤ X
• X + pal[X] / 2 ≥ Y

# Code: O(nlog2n) [17304KB, 1072MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

int n, ans = 0;
char str[500005];
int pal[500005];

inline void Manacher(char *str, int len){
str[0] = '\$';
int id = 0, mxr = 0;
for(register int i = 1; i <= len; i++){
pal[i] = (mxr >= i) ? min(mxr - i, pal[2 * id - i]) : 0;
while(str[i + pal[i] + 1] == str[i - pal[i]]) pal[i]++;
if(i + pal[i] > mxr) mxr = i + pal[i], id = i;
}
}  // Needn't insert special characters because the length of required substring is even

int Y[500005], topY;
set<int> S;

inline bool cmp(const int &a, const int &b) {return a - pal[a] < b - pal[b];}

int main(){
scanf("%d%s", &n, str + 1);
Manacher(str, n);
/*
let X be the left-side center of double palindrome substring(DPS) "wwRwwR"
let Y be the left-side center of the second "wwR" of the DPS
X and Y must abide the following relationship:
(1) Y - pal[Y] <= X
(2) X + pal[X] / 2 >= Y
*/
for(register int i = 1; i <= n; i++) Y[i] = i;
sort(Y + 1, Y + n + 1, cmp), topY = 1;
for(register int X = 1; X <= n; X++){
while(topY <= n && Y[topY] - pal[Y[topY]] <= X) S.insert(Y[topY++]);
set<int>::iterator maxY = S.upper_bound(X + (pal[X] >> 1)); maxY--;
ans = max(ans, *maxY - X << 2);
}
printf("%d\n", ans);
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai