基礎了解
- 回文串：是一個正讀和反讀都一樣的字符串。例如：level ，asdffdsa
- 回文子串：字符串中，滿足回文串條件的子串
優(yōu)勢
- 不用關注字符串的奇偶性
- 線性查找辐怕，每一個字符的回文串長度查找都只需一次，時間復雜度為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后，就是真正的字符串了翩伪。
通過上面的分析微猖，發(fā)現只要獲得字符的回文串半徑，就能夠計算并獲得最長的回文子串
如何計算回文子串半徑缘屹？
-
"材料準備"
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，如下圖：
那么說明以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位置開始一個一個進行匹配，直到發(fā)生失配留美，從而更新max_string_length_id和對應的max_string_id以及Len[i]彰檬。
2.2 i>max_string_id
如果i比max_string_length_id還要大，說明對于中點為i的回文串還一點都沒有匹配独榴，這個時候僧叉，就只能老老實實地一個一個匹配了，匹配完成后要更新max_string_length_id的位置和對應的max_string_id以及Len[i]棺榔。
代碼加工中...
借鑒如下博文瓶堕，如有興趣可以查看
http://blog.csdn.net/dyx404514/article/details/42061017
