最长回文子串python,最长回文子串c++语言

题目描述

对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。

给定字符串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 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 = 0; i--) { dp[i][i] = true; for (int j = i + 1; j 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 s_new = new ArrayList<>(); for(int i = 0;i 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 = 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) = 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