网页转向网站,保定定兴网站建设,人力资源管理系统入口,外贸开发网站开发这个算法题里面总是有
暴力解法
把所有字串都拿出来判断一下 这里有小小的优化#xff1a;
就是当判断的字串小于等于我们自己求得的最长回文子串的长度#xff0c;那么我们就不需要在进行对这个的判断这里的begin#xff0c;还可以用来取得最小回文子串是什么 java // 暴…这个算法题里面总是有
暴力解法
把所有字串都拿出来判断一下 这里有小小的优化
就是当判断的字串小于等于我们自己求得的最长回文子串的长度那么我们就不需要在进行对这个的判断这里的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(i1, len(s)):if maxLen j - i 1 and s[i:j] s[j:i:-1]:maxLen j-i1return 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, i1))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算法
这个算法
123456aabbaa
首先得知道几点
解决对称中心是数还是数中间。 我们可以在每一个中间插入一个#用#来代表2个数的中间就统一了起来。
123456#a#a#b#b#a#a#
算法我觉得是在中心扩展的衍生 先通过中心扩展找到前几个最大的dp然后通过已经求得的dp优化需要求得的数。 为了实现这个需要维护几个变量。已经求得的能够到最右边的回文子串的最右数、对称中心。 对称中心左右的在圈内的dp应该是一样的。如到7的时候可以得到最右为13中心为7.求dp【10】的时候由于对称其圈内的dp【10】dp【4】1如果这个dp大于右边界我们是不能确定的所以最大只能取右边界。然后在扩展
12345678910111213#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 ip[i] len(s)-1 and s[i-p[i]] s[ip[i]]:p[i] 1if i p[i] maxRight:maxRight i p[i]maxCeaanter imaxLen max(maxLen, p[i])return maxLen - 1
