bzoj 2565 最长双回文串

顺序和逆序读起来完全一样的串叫做回文串。比如 acbca 是回文串，而 abc 不是（abc 的顺序为 “abc” ，逆序为 “cba” ，不相同）。
输入长度为 n 的串 S ，求 S 的最长双回文子串 T, 即可将 T 分为两部分 X ， Y ，（ |X|,|Y|≥1 ）且 X 和 Y 都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数，表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

Hint

样例说明

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。

对于100%的数据，2≤|S|≤10^5

2015.4.25新加数据一组

　　题目大意 (题目太简洁不需要大意)

　　这几天学长们来讲字符串，然而我搞了几天数论(坏孩子一枚)，终于做了一道和主题相符的题目。

　　题目要求两个不想交且连续的回文串。Manacher？回文自动机?回文树(再见我们没有共同语言)？(等等，没对，怎么在套算法？)

　　根据常用的套路，我们可以考虑枚举中间的字符，然后查找位置i左侧(包括它自己)离它最远的回文中心minl[i]，再查找在它的右边离它的下一个字符(不能相交嘛)最远的回文中心。

　　现在我们只考虑一边怎么做，另一边就依葫芦画瓢就好了。

　　在进行各种搞回文串的算法的时候，找到某个位置i，得到它的最大半径为r(不算这个位置i本身)，那么位置i - r到位置i都多了一个选择i，然后对这个区间和i进行取min(更新)。

　　然后这个怎么做?线段树?(就算可以做我也懒得写)

　　然后接着思考吧。执行Manacher时，考虑两种情况

　　1)当前回文串的右端点没有超过R，显然当前它所在的一段之前早被别的回文串达到了，所以它对答案没什么贡献(我指的是某个位置左侧离它最远的回文中心)，不管。

　　2)如果当前回文串的右端点超过了R，那么就将超过的部分的minl全部设成i。想想为什么？因为越往后回文中心的编号在递增，即使它达到了那些位置也没什么用。

　　然后像这样，正反跑一遍Manacher就完事了。总时间复杂度O(n)(我也很好奇它为什么只出1e5的数据范围)

Code

 1 /**
 2  * bzoj
 3  * Problem#2565
 4  * Accepted
 5  * Time:76ms
 6  * Memory:3928k
 7  */
 8 #include <bits/stdc++.h>
 9 using namespace std;
10 #define smax(a, b) (a) = max((a), (b))
11 
12 int n = 0;
13 char str[100005];
14 char S[200005];
15 int rs[200005];
16 int minl[200005];
17 int maxr[200005];
18 
19 inline void init() {
20     gets(str);
21     int len = strlen(str);
22     S[n++] = '+';
23     for(int i = 0; i < len; i++)
24         S[n++] = '#', S[n++] = str[i];
25     S[n++] = '#';
26     S[n] = '-';
27     S[n + 1] = 0;
28 }
29 
30 inline void manacher(int* dis) {
31     int R = 0, pos = 0;
32     memset(rs, 0, sizeof(int) * (n + 1));
33     for(int i = 1; i < n; i++) {
34         if(i > R) {
35             dis[i] = i;
36             while(S[i - rs[i] - 1] == S[i + rs[i] + 1])    
37                 rs[i]++, dis[i + rs[i]] = i;
38             R = i + rs[i], pos = i;
39         } else {
40             if(i + rs[(pos << 1) - i] >= R) {
41                 rs[i] = R - i;
42                 while(S[i + rs[i] + 1] == S[i - rs[i] - 1])
43                     rs[i]++, dis[i + rs[i]] = i;
44                 if(i + rs[i] > R)
45                     R = i + rs[i], pos = i;
46             } else {
47                 rs[i] = rs[(pos << 1) - i];
48             }
49         }
50     }
51 }
52 
53 inline void solve() {
54     manacher(minl);
55     reverse(S, S + n + 1);
56     manacher(maxr);
57     reverse(maxr, maxr + n + 1);
58     int res = 0;
59     for(int i = 1; i < n - 1; i++) {
60         smax(res, n - maxr[i + 1] - minl[i]);
61     }
62     printf("%d
", res);
63 }
64 
65 int main() {
66     init();
67     solve();
68     return 0;
69 }