基础了解
- 回文串：是一个正读和反读都一样的字符串。例如：level ，asdffdsa
- 回文子串：字符串中，满足回文串条件的子串
优势
- 不用关注字符串的奇偶性
- 线性查找，每一个字符的回文串长度查找都只需一次，时间复杂度为O(n)
如何进行字符串处理
- 通过对字符串进行预处理，即在每一个字符前后都插上相同的符号，这样会让字符串都变成奇数长度。
abcde ---> #a#b#c#d#e#
abcd ---> #a#b#c#d#
求最大回文子串思路
- 求每一个字符所能获得的最大回文串的半径
- 根据半径-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 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.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
