算法--最长回文子串--java--python

这个算法题里面总是有

暴力解法

把所有字串都拿出来判断一下
这里有小小的优化：

• 就是当判断的字串小于等于我们自己求得的最长回文子串的长度，那么我们就不需要在进行对这个的判断
• 这里的begin，还可以用来取得最小回文子串是什么
  java

    // 暴力解法最长回文子串public static int longestPalindrome(String s) {int len = s.length();if (s.length() < 2)return len;int maxLen = 1;int begin = 0;char[] chars = s.toCharArray();for (int i = 0; i < len; i++) {for (int j = i + 1; j < len; j++) {if (validPalindromic(chars, i, j))maxLen = Math.max(maxLen, j - i + 1);begin = i;}}return maxLen;}// 验证子串 s[left..right] 是否为回文串private static boolean validPalindromic(char[] chars, int left, int right) {while (left < right) {if (chars[left] != chars[right]) {return false;}left++;right--;}return true;}

python

def longestPalindrome(s: str) -> int:if len(s) < 2:return len(s)maxLen = 0for i in range(len(s)):for j in range(i+1, len(s)):if maxLen < j - i + 1 and s[i:j] == s[j:i:-1]:maxLen = j-i+1return maxLens = input()
print(longestPalindrome(s))

中心扩散法

以某数或者某2个数为中心进行扩散判断

    // 中心扩散法最长回文子串public static int longestPalindrome2(String s) {int len = s.length();if (s.length() < 2)return len;int maxLen = 1;char[] chars = s.toCharArray();for (int i = 0; i < len; i++) {maxLen = Math.max(maxLen, expandAroundCenter(chars, i, i));maxLen = Math.max(maxLen, expandAroundCenter(chars, i, i + 1));}return maxLen;}private static int expandAroundCenter(char[] charArray, int left, int right) {while (left >= 0 && right < charArray.length && charArray[left] == charArray[right]) {left--;right++;}return right - left -1;}

python

# 中心扩展法
def longestPalindrome(s: str) -> int:if len(s) < 2:return len(s)maxLen = 0for i in range(len(s)):maxLen = max(maxLen, expand(s, i, i))maxLen = max(maxLen, expand(s, i, i+1))return maxLendef expand(s: str, left: int, right: int) -> int:while left >= 0 and right < len(s) and s[left] == s[right]:left -= 1right += 1return right - left - 1s = input()
print(longestPalindrome(s))

manacher算法

这个算法

1	2	3	4	5	6
a	a	b	b	a	a

首先得知道几点：

• 解决对称中心是数还是数中间。
  我们可以在每一个中间插入一个#，用#来代表2个数的中间，就统一了起来。

1	2	3	4	5	6
#a	#a	#b	#b	#a	#a#

• 算法我觉得是在中心扩展的衍生
  先通过中心扩展找到前几个最大的dp，然后通过已经求得的dp优化需要求得的数。
  为了实现这个需要维护几个变量。已经求得的能够到最右边的回文子串的最右数、对称中心。
  • 对称中心左右的在圈内的dp应该是一样的。
  • 如到7的时候可以得到最右为13中心为7.
  • 求dp【10】的时候由于对称其，圈内的dp【10】=dp【4】=1
  • 如果这个dp大于右边界，我们是不能确定的，所以最大只能取右边界。然后在扩展

1	2	3	4	5	6	7	8	9	10	11	12	13
#	a	#	a	#	b	#	b	#	a	#	a	$

在求新数的时候，如果这个数在这个最右子串里面，

    // manacher算法最长回文子串public static int longestPalindrome(String s) {if (s.length() < 2)return s.length();// 预处理StringBuilder sb = new StringBuilder();sb.append("@#");for (int i = 0; i < s.length(); i++) {sb.append(s.charAt(i));sb.append('#');}sb.append("#$");char[] chars = sb.toString().toCharArray();int len = chars.length;int[] dp = new int[len];int maxCenter = 0, maxRight = 0, maxLen = 0;for (int i = 1; i < len - 1; i++) {dp[i] = maxRight > i ? Math.min(dp[2 * maxCenter - i], maxRight - i) : 1;while (chars[i + dp[i]] == chars[i - dp[i]])dp[i]++;if (maxRight < i + dp[i]) {maxRight = i + dp[i];maxCenter = i;}maxLen = Math.max(maxLen, dp[i]);}return maxLen - 1;}

# manacher算法
def longestPalindrome(s: str) -> int:if len(s) < 2:return len(s)s = "@#" + '#'.join(s) + "#$"  # 预处理maxLen = 0maxRight = 0maxCenter = 0p = [0] * len(s)for i in range(1,len(s)-1):if i < maxRight:p[i] = min(p[2 * maxCenter - i], maxRight - i)else:p[i] = 1# 不懂为什么这个不加前面的条件就通不过while i-p[i] > 0 and i+p[i] < len(s)-1 and s[i-p[i]] == s[i+p[i]]:p[i] += 1if i + p[i] > maxRight:maxRight = i + p[i]maxCeaanter = imaxLen = max(maxLen, p[i])return maxLen - 1