最长回文

Problem Description

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等

Input

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S 两组case之间由空行隔开(该空行不用处理) 字符串长度len <= 110000

Output

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input

aaaa

abab

Sample Output

4 3

下面简单说下看了Manacher算法的想法，我是通过 https://www.felix021.com/blog/read.php?2040 学到的，具体的学习可以参考该博客。

当时一看这个算法觉得十分厉害啊，先把我们要求的字符串先预处理一下，把无论奇偶长度的字符串都变成奇数长度的，就是例如样例，我们把“aaaa”变成“#a#a#a#a#”，这样来处理成一个新的字符串S，然后再用一个数组P来表示当在S【i】的时候，以S【i】为中心的最长回文子串向左右扩张的最大长度，例如上面的例子，当i = 5的时候，P【5】= 5，当i = 2的时候P【i】= 2，所以明显地可以看到，我们以S【i】为中心对折对应的回文子串，对折之后的长度就是P【i】（算长度的时候在S【i】自己也是要算一位的）。那么我们可以发现，P【i】- 1表示的就是原字符串的回文子串长度。

接下来就是比较重点的地方就是算P【i】。在这里引入两个变量 id，xr，xl。id表示目前能够得到的最长的回文子串的中心，xr是该回文子串的右边界。即 xr = id + P【id】，同理xl是该回文子串的左边界，即xl = id - P【id】。

当 i < xr 的时候，我们设一个变量 j = id * 2 - i = id + （id - i），即 j 是 i 以 id 为对称点翻折过去的位置，因为我们跑到 i 这个位置的时候，前面的 P【j】肯定被更新过了，那么可以根据P【j】和 xr - i 的关系来判断P【i】的长度。

如果P【j】 > xr - i的话，那么意味着以 j 为中心的回文子串不完全包含在以 id 为中心的回文子串里面，那么我们并不能就这样完全判断出P【i】的长度了，我们只能够了解到，因为 i < xr ，所以 j > xl，所以以 j 为中心的回文子串是有一部分包含在以 id 为中心的回文子串里边的，那么只能保证 P【i】的长度是至少有 xr - i 那么长的。至于剩下还有多长，只能用一个循环再去匹配更新P【i】了。

如果P【j】 < xr - i的话，那么相当于以 j 为中心的回文子串完全包含在了以 id 为中心的回文子串里边，又因为 i 和 j 是关于 id 对称的并且回文串的一边和另一边是相同的，所以P【i】的长度可以直接求得等于P【j】了。

所以在 i < xr 的情况下，我们可以总结得到 P【i】= min（P【j】，xr - i ）。其中 j = id * 2 - i。

上面都是 xr > i 的情况，那么 xr < i 的情况我们未知，只能设P【i】只包含自己本身即等于1，然后慢慢去匹配了。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define N 110010
 6 char str[N];
 7 char s[2*N];
 8 int p[2*N];
 9 int l;
10 //求最长回文子串的Manacher算法
11 void init()
12 {
13     memset(p, 0, sizeof(p));
14     int len = strlen(str);
15     s[0] = '%';
16     l = 1;
17     for(int i = 0; i < len; i++) {
18         s[l++] = '#';
19         s[l++] = str[i];
20     }
21     s[l++] = '#';
22     s[l] = '';
23 }
24 
25 int manacher()
26 {
27     init();
28     int xr = 0, id = 0;
29     for(int i = 1; s[i]; i++) {
30         p[i] = xr > i ? min(p[id*2-i], xr - i) : 1;
31         while(s[i+p[i]] == s[i-p[i]]) p[i]++;
32         if(i + p[i] > xr) {
33             xr = i + p[i];
34             id = i;
35         }
36     }
37     int ans = 0;
38     for(int i = 1; i < l; i++) {
39         if(p[i] - 1 > ans) ans = p[i] - 1;
40     }
41     return ans;
42 
43 }
44 
45 int main()
46 {
47     while(~scanf("%s", str))
48         printf("%d
", manacher());
49     return 0;
50 }