共计 5437 个字符，预计需要花费 14 分钟才能阅读完成。
这篇文章主要讲解了“Java 最长回文子串怎么实现”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着丸趣 TV 小编的思路慢慢深入，一起来研究和学习“Java 最长回文子串怎么实现”吧！
/**
*
* 最长回文子串
*
* 著名的 Manacher 算法 O(N) 时间 O(N) 空间
*/
public class LongestPalindrome { public static void main(String[] args) { LongestPalindrome lp = new LongestPalindrome();
System.out.println(lp.longestPalindrome( babcbabcbaccba));
//qgjjgq
}
/**
* 一个 O(N) 的算法 (Manacher)
*
*
*/
// Transform S into T.
// For example, S = abba , T = ^#a#b#b#a#$ .
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
// String preProcess(String s) {// int n = s.length();
// if (n == 0) return ^$
// String ret = ^
// for (int i = 0; i n; i++)
// {// ret += # + s.substring(i, i + 1);
// }
// ret += #$
// return ret;
// }
// public String longestPalindrome(String s) {// String T = preProcess(s);
// System.out.println(T);
// int length = T.length();
// int[] p = new int[length];
// int C = 0, R = 0;
// for (int i = 1; i length - 1; i++)
// {// int i_mirror = C - (i - C);
// int diff = R - i;
// if (diff = 0)// 当前 i 在 C 和 R 之间，可以利用回文的对称属性
// {// if (p[i_mirror] diff)// i 的对称点的回文长度在 C 的大回文范围内部
// { p[i] = p[i_mirror]; }
// else
// {// p[i] = diff;
// // i 处的回文可能超出 C 的大回文范围了
// while (T.charAt(i + p[i] + 1) == T.charAt(i - p[i] - 1))
// { p[i]++; }
// C = i;
// R = i + p[i];
// }
// }
// else
// {// p[i] = 0;
// while (T.charAt(i + p[i] + 1) == T.charAt(i - p[i] - 1))
// { p[i]++; }
// C = i;
// R = i + p[i];
// }
// }
// int maxLen = 0;
// int centerIndex = 0;
// for (int i = 1; i length - 1; i++) {// if (p[i] maxLen) {// maxLen = p[i];
// centerIndex = i;
// }
// }
// return s.substring((centerIndex - 1 - maxLen) / 2, (centerIndex - 1 - maxLen) / 2 + maxLen);
// }
/***
* 3. 中心扩展法
因为回文字符串是以中心轴对称的，所以如果我们从下标 i 出发，用 2 个指针向 i 的两边扩展判断是否相等，那么只需要对 0 到
n- 1 的下标都做此操作，就可以求出最长的回文子串。但需要注意的是，回文字符串有奇偶对称之分，即 abcba 与 abba 2 种类型， 因此需要在代码编写时都做判断。 设函数 int Palindromic ( string s, int i ,int j) 是求由下标 i 和 j 向两边扩展的回文串的长度，那么对 0 至 n - 1 的下标，调用 2 次此函数： int lenOdd = Palindromic( str, i, i ) 和 int lenEven = Palindromic (str , i , j )，即可求得以 i 下标为奇回文和偶回文的子串长度。 接下来以 lenOdd 和 lenEven 中的最大值与当前最大值 max 比较即可。 这个方法有一个好处是时间复杂度为 O(n2)，且不需要使用额外的空间。 */
// public String longestPalindrome(String s) {// if (s.isEmpty()) {
// return null;
// }
// if (s.length() == 1) {
// return s;
// }
// String longest = s.substring(0, 1);
// for (int i = 0; i s.length(); i++) {
// // get longest palindrome with center of i
// String tmp = helper(s, i, i);
// if (tmp.length() longest.length()) {
// longest = tmp;
// }
// // get longest palindrome with center of i, i+1
// tmp = helper(s, i, i + 1);
// if (tmp.length() longest.length()) {
// longest = tmp;
// }
// }
// return longest;
// }
// // Given a center, either one letter or two letter,
// // Find longest palindrome
// public static String helper(String s, int begin, int end) {// while (begin = 0 end = s.length() - 1
// s.charAt(begin) == s.charAt(end)) {
// begin--;
// end++;
// }
// String subS = s.substring(begin + 1, end);
// return subS;
// }
* 2. 动态规划法
假设 dp[ i ][ j ] 的值为 true，表示字符串 s 中下标从 i 到 j 的字符组成的子串是回文串。那么可以推出： dp[ i ][ j ] = dp[ i + 1][ j - 1] s[ i ] == s[ j ]。 这是一般的情况，由于需要依靠 i +1, j -1，所以有可能 i + 1 = j -1, i +1 = (j - 1) -1，因此需要求出基准情况才能套用以上的公式： a. i + 1 = j -1，即回文长度为 1 时，dp[ i ][ i ] = true;
b. i +1 = (j - 1) -1，即回文长度为 2 时，dp[ i ][ i + 1] = （s[ i ] == s[ i + 1]）。 有了以上分析就可以写出代码了。需要注意的是动态规划需要额外的 O(n2) 的空间。 */
public String longestPalindrome(String s) { if (s == null)
return null;
if(s.length() =1)
return s;
int maxLen = 0;
String longestStr = null;
int length = s.length();
int[][] table = new int[length][length];
//every single letter is palindrome
for (int i = 0; i length; i++) { table[i][i] = 1;
}
printTable(table);
//e.g. bcba
//two consecutive(连续) same letters are palindrome
for (int i = 0; i = length - 2; i++) { // 注意 i = length - 2, 是因为循环里面有用到 s.charAt(i+1), 避免数组越界
//System.out.println(i= +i+ +s.charAt(i));
//System.out.println(i= +i+ +s.charAt(i+1));
if (s.charAt(i) == s.charAt(i + 1)){ table[i][i + 1] = 1;
longestStr = s.substring(i, i + 2);
}
}
System.out.println(longestStr: +longestStr);
printTable(table);
//condition for calculate whole table
for (int l = 3; l = length; l++) { // l 表示区间的长度从 3 开始
for (int i = 0; i = length-l; i++) {
int j = i + l - 1;
if (s.charAt(i) == s.charAt(j)) { table[i][j] = table[i + 1][j - 1];
if (table[i][j] == 1 l maxLen) // 比较 maxLen
longestStr = s.substring(i, j + 1);
} else { table[i][j] = 0;
}
// printTable(table);
}
}
return longestStr;
}
public static void printTable(int[][] x){ for(int [] y : x){ for(int z: y){
System.out.print(z +
}
System.out.println();
}
System.out.println( ------
}
/***
* 1. 两侧比较法
以 abba 这样一个字符串为例来看，abba 中，一共有偶数个字，第 1 位 = 倒数第 1 位，第 2 位 = 倒数第 2 位...... 第 N 位 = 倒数第 N 位
以 aba 这样一个字符串为例来看，aba 中，一共有奇数个字符，排除掉正中间的那个字符后，第 1 位 = 倒数第 1 位...... 第 N 位 = 倒数第 N 位
所以，假设找到一个长度为 len1 的子串后，我们接下去测试它是否满足，第 1 位 = 倒数第 1 位，第 2 位 = 倒数第 2 位...... 第 N 位 = 倒数第 N 位，也就是说，去测试从头尾到中点，字符是否逐一对应相等。 *
*
* TL
*/
// public String longestPalindrome(String s) {
// int max = 0;
// String maxp =
// if (s.length() = 1) return s;
// for (int i = 0; i s.length(); i++){// for (int j = i + 1; j s.length(); j++){// boolean flag = isPalindrome(s.substring(i,j+1)); //substring 是左闭右开的空间
// if (flag){// if (max j - i){// maxp = s.substring(i,j+1);
// max = j - i;
// }
// }
// }
// }
// return maxp;
// }
// private boolean isPalindrome(String str) { // baab 03 12 cbabc 04 13
// for (int i = 0; i (str.length()/2);i++){// if (str.charAt(i) != str.charAt(str.length() - i - 1)){
// return false;
// }
// }
// return true;
// }
}感谢各位的阅读，以上就是“Java 最长回文子串怎么实现”的内容了，经过本文的学习后，相信大家对 Java 最长回文子串怎么实现这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是丸趣 TV，丸趣 TV 小编将为大家推送更多相关知识点的文章，欢迎关注！
正文完
