最大回文子串算法Manacher

基础了解

1. 回文串：是一个正读和反读都一样的字符串。例如：level ，asdffdsa
2. 回文子串：字符串中，满足回文串条件的子串

优势

1. 不用关注字符串的奇偶性
2. 线性查找，每一个字符的回文串长度查找都只需一次，时间复杂度为O(n)

如何进行字符串处理

1. 通过对字符串进行预处理，即在每一个字符前后都插上相同的符号，这样会让字符串都变成奇数长度。

abcde ---> #a#b#c#d#e#
abcd ---> #a#b#c#d#

求最大回文子串思路

1. 求每一个字符所能获得的最大回文串的半径
2. 根据半径-1，就可以得到以该字符为中心的最长回文串长度(半径-1)

为什么字符的最长回文子串会是半径-1

• 观察下面子串
  *char： *字符串的各个字符
  *RL： *以该字符为中心，获取回文子串半径(如果只有自身，为1)
  *i： *字符序号

char	#	a	#	b	#	a	#
RL	1	2	1	4	1	2	1
RL-1	0	1	0	3	0	1	0
i	0	1	2	3	4	5	6

• 以b字符为例，b字符的回文子串有#a#b#a# ，去掉加入的#，实际上为aba(3个)。b的半径按从左到右为b#a#(4个)，所以，字符的最长回文子串为RL(半径-1)
• (#a#b#a#)中#跟a对应，#跟b对应，#跟a对应，所以字符的回文长度可为(L(回文串长度)-1)/2。先去掉一个#，剩下的对半除以2后，就是真正的字符串了。

通过上面的分析，发现只要获得字符的回文串半径，就能够计算并获得最长的回文子串

如何计算回文子串半径？

1. "材料准备"
   1.1 i：字符序号
   1.2 max_string_id：最大回文子串的字符的位置
   1.3 max_string_length_id：最大回文子串，所能触及的最右一个字符的位置
   1.4 2max_string_length_id-max_string_id：最大回文子串，所能触及的最左一个字符的位置
   1.5 Len：存储改造后的字符的数组*
   1.6 j：i以max_string_id中心的对称点
2. 两种情况分析
   2.1 i<max_string_id
   那么找到i相对于max_string_id的对称位置，设为j，那么如果Len[j]<P-i，如下图：

first.jpg

那么说明以j为中心的回文串一定在以max_string_id为中心的回文串的内部，且j和i关于位置max_string_id对称，由回文串的定义可知，一个回文串反过来还是一个回文串，所以以i为中心的回文串的长度至少和以j为中心的回文串一样，即Len[i]>=Len[j]。因为Len[j]<max_string_length_id-i,所以说i+Len[j]<max_string_length_id。由对称性可知Len[i]=Len[j]。

---

如果Len[j]>=max_string_length_id-i,由对称性，说明以i为中心的回文串可能会延伸到max_string_length_id之外，而大于max_string_length_id的部分我们还没有进行匹配，所以要从max_string_length_id+1位置开始一个一个进行匹配，直到发生失配，从而更新max_string_length_id和对应的max_string_id以及Len[i]。

second.jpg

2.2 i>max_string_id
如果i比max_string_length_id还要大，说明对于中点为i的回文串还一点都没有匹配，这个时候，就只能老老实实地一个一个匹配了，匹配完成后要更新max_string_length_id的位置和对应的max_string_id以及Len[i]。

third.jpg

---

代码加工中...

---

借鉴如下博文，如有兴趣可以查看
http://blog.csdn.net/dyx404514/article/details/42061017