o(n)时间复杂度求最长回文子串的manacher算法:
public class Solution { public String longestPalindrome(String s) { if(s.length()==0) return ""; StringBuffer sb=new StringBuffer(); for(int i=0;i<s.length();i++){ sb.append('$').append(s.charAt(i)); if(i==s.length()-1) sb.append('$'); } int id=0,edge=1; int idRe=0,maxRe=1; s=sb.toString(); int[] dp=new int[s.length()]; dp[0]=1; for(int i=1;i<s.length();i++){ if(i<edge){ dp[i]=Math.min(dp[id*2-i],edge-i); }else{ dp[i]=1; } while(i-dp[i]>=0&&i+dp[i]<s.length()&&s.charAt(i-dp[i])==s.charAt(i+dp[i])){ dp[i]++; } if(dp[i]+i>edge){ id=i; edge=dp[i]+i; } if(maxRe<dp[i]){ maxRe=dp[i]; idRe=id; } } StringBuffer re=new StringBuffer(); int start=idRe-maxRe+2; for(int i=start;i<=idRe*2-start;i+=2){ re.append(s.charAt(i)); } return re.toString(); } }
