继续补充一些题目简单但思路丰富的题目，很有标志性的字符串回文问题。学习了一下Manacher算法。
题目(LeetCode No.5)
中心扩展法
首先是最简单思路，时间复杂度为O(n^3)的暴力法。选择所有能出现的字符子串的集合，依次检验是否为回文串，然后取长度最大者。共有 n(n-1)/2 个不同的子串，验证子串消耗为O(n)。
我觉得第二好理解的思路其实是中心扩展法。相比动态规划来说，中心扩展的思路只要明白回文左右互为镜像，在一次循环遍历中将每一个经过的点当做回文的中点，然后向左右两边伸展判断即可。在开头、结尾和字符串的每个字符之间插入‘#’可以无视子字符串是奇数还是偶数个。（‘#’可以是任意字符串中不会出现的符号。）
因为很直白所以直接给出Leetcode的题解。
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return ""; //非空判定
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i); //对中心为奇和偶都进行讨论
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) { //判断是否为当前最长子串，是则记录下标
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
//判断以i或（i和i+1）为中心的子串的长度
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
动态规划
动态规划其实就是暴力遍历的优化。无论是动态规划还是Manacher算法，核心思路就是最大化利用已求出过的结论，减少重复计算，无非是Manacher算法的利用效率比动态规划更高。
使用DP解题没有思路时，首先找三要素：
最优子结构、边界、状态转移方程
对于任何一个回文串 S(i , j)，其 S(i+1 , j-1)一定为 回文串。反之：
S (i , j) = S(i+1 , j-1) && Si==Sj
边界即为S(i+1 , j-1)为一个字母或两个字母的回文串。
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
String answer = "";
boolean[][] dp = new boolean[len][len];
for(int i = 0 ;i < len; i++){
for(int j = i; j >= 0 ;j--){
if(s.charAt(i) == s.charAt(j)&&(i-j < 2 || dp[i-1][j+1]))
dp[i][j] = true;
if (dp[i][j] && (i-j+1 > answer.length())){
answer = s.substring(j,i+1);
}
}
}
return answer;
}
}
Manacher算法
最后是Manacher算法。看完算法思路之后我写了一个我自己觉得更容易理解的版本，代码量会稍微多几行。
class Solution {
public String longestPalindrome(String s) {
if(s.length()==0){ //非空判定
return "";
}
int maxlen = 0, c = 0, max = 0, index = 0;
int len = 2*s.length()+2;
int[] p = new int[len]; //p数组记录每一个点的回文半径
char[] chars = new char[len];
chars[0] = '$'; //头插入'$'符号处理符号组
for(int i=0;i<s.length();i++){ //每个字符之间插入'#'符号方便统一奇偶
chars[2*i+1] = s.charAt(i);
chars[2*i+2] = '#';
}
for(int i=1;i<len;i++){ //当前下标以越过曾经处理过的最远端，
if(i>=maxlen){ //即之后的位置并未到达过
p[i] = getR(i,chars,1); //未到达所以需要从半径1开始左右对比
}
else{ //当前下标在曾经到达过的字符串里
int r = Math.min(p[2*c-i],maxlen-i);//直接利用记录过的回文半径
p[i] = getR(i,chars,r);//能直接利用的极限是曾经到达过的最远端
}
if(p[i]+i>maxlen){
c = i; //更新当前延展到最远端的回文串的中心下标
maxlen = p[i]+i;//更新到达过最远端的极限
}
}
for(int i=0;i<len;i++){ //寻找回文半径最长的子字符串的中心下标
if(p[i]>max){
max = p[i];
index = i;
}
}
String answer = s.substring((index-max+1)/2,(index+max)/2);
return answer;
}
//getR函数为对中心下标为i的子字符串进行左右延伸，计算它的最大回文半径
//r则为当前可直接跳至的回文半径（因为<r的部分已处理过，所以可以直接跳）
public int getR(int i,char[] chars,int r){
int left = i-r;
int right = i+r;
int R = r;
if(left<0||right>=chars.length){
return R;
}
while(chars[left]==chars[right]){
R++;
left--;
right++;
if(right>=chars.length||left<0){
break;
}
}
return R;
}
}
递交结果
