对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
给定字符串A以及它的长度n，请返回最长回文子串的长度。
测试样例：
"abc1234321ab",12 返回：7 CODE 暴力求解一： 2682ms5752KB# -*- coding:utf-8 -*-class Palindrome: def getLongestPalindrome(self, A, n): # write code here if n <= 1: return n s = int(n /2) max_n = 0 arr = list(A) for i in range(n-1): i += 1 step = min(s, n - i) for j in range(step): j+=1 c = arr[i] tr = arr[i+1 : i+j+1] tl = arr[i+1 : i+j+1] tl.reverse() c1 = [] c2 = [] c1.extend(tl) c1.extend(c) c1.extend(tr) c2.extend(tl) c2.extend(c) c2.extend(c) c2.extend(tr) if ("".join(c1) in A): max_n = max(max_n, len(c1)) elif ("".join(c2) in A): max_n = max(max_n, len(c2)) return max_n 暴力求解二： 211ms32072KB public int getLongestPalindrome(String s) { if(s == null){ return 0; } if(s.length() <= 1) return s.length(); String res=s.substring(0,1); for (int i = 0; i < s.length(); i++) { for (int j = i + 1; j <= s.length(); j++) { String k=s.substring(i,j); String rk=new StringBuffer(k).reverse().toString(); if(k.equals(rk)&&k.length()>res.length()){ res=k; } } } return res.length(); } 暴力求解三： 115ms29352KBpublic int getLongestPalindrome(String s) { if (s == null) return 0; if(s.length() <= 1) return s.length(); for(int i = s.length();i > 0; i--) {//子串长度 for (int j = 0; j <= s.length() - i; j++) { String sub = s.substring(j , i + j);//子串位置 int count = 0;//计数，用来判断是否对称 for (int k = 0; k < sub.length() / 2; k++) {//左右对称判断 if (sub.charAt(k) == sub.charAt(sub.length() - k - 1)) count++; } if (count == sub.length() / 2) return sub.length(); } } return 1; } 动态规划： 38ms11376KB public int getLongestPalindrome(String s) { if (s == null) { return 0; } if (s.length() <= 1) { return s.length(); } int n = s.length(); boolean[][] dp = new boolean[n][n]; int left = 0; int right = 0; for (int i = n - 2; i >= 0; i--) { dp[i][i] = true; for (int j = i + 1; j < n; j++) { dp[i][j] = s.charAt(i) == s.charAt(j) &&( j-i<3||dp[i+1][j-1]);//小于3一定是回文 if(dp[i][j]&&right-left<j-i){ left=i; right=j; } } } return right - left + 1; } Manacher算法(原文：https://blog.csdn.net/qq_32354501/article/details/80084325) 31ms9832KBpublic int getLongestPalindrome(String s) { if (s == null) { return 0; } if (s.length() <= 1) { return s.length(); } List<Character> s_new = new ArrayList<>(); for(int i = 0;i < s.length();i++){ s_new.add('#'); s_new.add(s.charAt(i)); } s_new.add('#'); List<Integer> Len = new ArrayList<>(); String sub = "";//最长回文子串 int sub_midd = 0;//表示在i之前所得到的Len数组中的最大值所在位置 int sub_side = 0;//表示以sub_midd为中心的最长回文子串的最右端在S_new中的位置 Len.add(1); for(int i = 1;i < s_new.size();i++){ if(i < sub_side) {//i < sub_side时，在Len[j]和sub_side - i中取最小值，省去了j的判断 int j = 2 * sub_midd - i; if(j >= 2 * sub_midd - sub_side && Len.get(j) <= sub_side - i){ Len.add(Len.get(j)); } else Len.add(sub_side - i + 1); } else//i >= sub_side时，从头开始匹配 Len.add(1); while( (i - Len.get(i) >= 0 && i + Len.get(i) < s_new.size()) && (s_new.get(i - Len.get(i)) == s_new.get(i + Len.get(i)))) Len.set(i,Len.get(i) + 1);//s_new[i]两端开始扩展匹配，直到匹配失败时停止 if(Len.get(i) >= Len.get(sub_midd)){//匹配的新回文子串长度大于原有的长度 sub_side = Len.get(i) + i - 1; sub_midd = i; } } sub = s.substring((2*sub_midd - sub_side)/2,sub_side /2);//在s中找到最长回文子串的位置 return sub.length(); }思想
参考文章：https://blog.csdn.net/SeaSky_Steven/article/details/108603928