@(leetcode)[字符串，动态规划，manacher算法]
leetcode 5 Longest Palindromic Substring
方法一：暴力解法 (Time Limit Exceeded 超时错误解法)
算法描述：从0到n取每一个可能的start和end，对所有子字符串，调用isPalindromic（）函数判断是否属于回文字符串，如果是回文串，且长度大于已知的最长字串，则取代成为目前最大回文子串。遍历之后返回最长的子回文串。算法时间复杂度不满足要求，会超时。
对回文串是否相等的isPalindromic函数判断方法为：两个指针从头尾开始向中间靠近，依次判断每个位置的字符是否相等，直到指针交会。
时间复杂度：O(n^3)
class Solution {
public String longestPalindrome(String s) {
int ans =0;
String ansString="";
for (int i=0;i<s.length();i++){
for(int j=i;j<s.length();j++){
if(isPalindromic(s.substring(i,j+1))){
if((j-i+1)>ans){
ansString=s.substring(i,j+1);
ans=j-i+1;
}
}
}
}
return ansString;
}
public boolean isPalindromic(String s){
int i=0,j=s.length()-1;
while (i<=j){
if(s.charAt(i)==s.charAt(j)){
i++;j--;
}else{return false;}
}
return true;
}
}
方法二：暴力解法+剪枝
算法描述：方法一的暴力解法会超时，通过剪枝可以适当降低时间复杂度。
1、在方法一中，每次end的起始位置都是从start位置开始。但是我们在求最长子串的过程中，会存储ans（已知的最长子回文串长度），长度小于ans的子串不需要再进行判断。所以end可以从start+ans的位置开始。
2、回文串的判断方法是调用isPalindromic()函数进行判断，函数之间的调用加载也需要消耗时间，因此在调用之前加上end位置的字符与start位置字符匹配判断，先进行一轮筛选，减少函数调用。（与时间复杂度无意义，但是在实际运行中可以减少开销。）
class Solution {
public String longestPalindrome(String s) {
int ans =0;
String ansString="";
for (int i=0;i<s.length()-ans;i++){
for(int j=i+ans;j<s.length();j++){//剪枝1、end从start+ans的位置开始
if(s.charAt(i)!=s.charAt(j))continue;//剪枝2、减少函数调用开销，如果end位置的字符与start位置字符不相等，则不可能是回文串。
if(isPalindromic(s.substring(i,j+1))){
if((j-i+1)>ans){
ansString=s.substring(i,j+1);
ans=j-i+1;
}
}
}
}
return ansString;
}
public boolean isPalindromic(String s){
int i=0,j=s.length()-1;
while (i<=j){
if(s.charAt(i)==s.charAt(j)){
i++;j--;
}else{return false;}
}
return true;
}
}
方法四：manacher算法
算法描述：Manacher算法是时间复杂度为O(n)的求最长回文字串算法，核心思想是充分利用已经判断的回文序列，减少回文序列判断次数（动态规划），算法步骤如下。
1、回文串有两种构成，一种是类似“bab”的奇数字符个数的回文串，一种是类似“baab”的偶数个数的回文串，为了后续不再讨论奇偶，manacher算法的第一步是将字符串每个字符前后都加上“#”字符，例如#b#a#b#（bab） 、（#b#a#a#b#）baab，拓展后的字符串统一为奇数字符，不妨将新串String 命名为t，新字符串长度t_length = s_length2+1；
2、对于t字符串中的每个字符t[i]，求回文半径，即以t[i]为中心的最大回文串的半径，不妨命名为radius[i]，其中radius[i]的长度包括了i字符本身。
所以，最长回文串的长度len = radius[i]2-1;
radius[i]的求法：
(a)首先根据已经求得的radius数组radius[0~i-1]，获取 radius[i]的最小半径。核心思想是：回文数组的半径也随中心对称
radius[i]= i<=Mx?Math.min(Mx-i+1,radius[2*center-i]):1;
如上图所示，字符串s="babcbabcbaccba"
求radius[8]时，可以参考已求得的radius[]数组中，center中心为7，最长覆盖范围为14。且radius[6]=1，
则radius[8]=radius[6]是必定符合条件的。
(b)判断radius[i]是否还能更长
class Solution {
public static String longestPalindrome(String s) {
//处理边界值
if(null==s||s.length()<1)return "";
//将s拓展为包含“#”的t串
String t= "";
for(int i=0;i<s.length();i++){
t= t+"#"+s.charAt(i);
}
t+="#";
//求半径数组
int Mx = 0;
int center = 0;
int[] radius = new int[t.length()];
int Max_index = 0;
int Max_radius = 0;
for(int i =0 ;i<radius.length;i++){
//获取radius[i]的起始值
radius[i]= i<=Mx?Math.min(Mx-i+1,radius[2*center-i]):1;
//拓展t[i],以radius[i]为起始半径
while(i-radius[i]>-1&&i+radius[i]<t.length()){
if(t.charAt(i-radius[i])==t.charAt(i+radius[i])){
radius[i]++;
}else{
break;
}
}
//更新center和Mx
if(i+radius[i]>Mx){
Mx = i+radius[i]-1;
center = i;
}
if(radius[i]>radius[Max_index])
{
Max_index=i;
}
}
int start = (Max_index-radius[Max_index]+1)/2;
int end = start + radius[Max_index]-1;
return s.substring(start,end);
}
}
