溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“Java最長回文子串怎么實現(xiàn)”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java最長回文子串怎么實現(xiàn)”吧！
/**
*
* 最長回文子串
*
* 著名的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的大回文范圍內(nèi)部
// { 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 出發(fā)，用2個指針向 i 的兩邊擴展判斷是否相等，那么只需要對0到
n-1的下標都做此操作，就可以求出最長的回文子串。但需要注意的是，回文字符串有奇偶對稱之分，即"abcba"與"abba"2種類型，
因此需要在代碼編寫時都做判斷。
設函數(shù)int Palindromic ( string &s, int i ,int j) 是求由下標 i 和 j 向兩邊擴展的回文串的長度，那么對0至n-1的下標，調(diào)用2次此函數(shù)：
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.動態(tài)規(guī)劃法
假設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]）。
有了以上分析就可以寫出代碼了。需要注意的是動態(tài)規(guī)劃需要額外的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(連續(xù)) same letters are palindrome
for (int i = 0; i <= length - 2; i++) { //注意 i<= length - 2,是因為循環(huán)里面有用到s.charAt(i+1),避免數(shù)組越界
//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表示區(qū)間的長度從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.兩側(cè)比較法
以abba這樣一個字符串為例來看，abba中，一共有偶數(shù)個字，第1位=倒數(shù)第1位，第2位=倒數(shù)第2位......第N位=倒數(shù)第N位
以aba這樣一個字符串為例來看，aba中，一共有奇數(shù)個字符，排除掉正中間的那個字符后，第1位=倒數(shù)第1位......第N位=倒數(shù)第N位
所以，假設找到一個長度為len1的子串后，我們接下去測試它是否滿足，第1位=倒數(shù)第1位，第2位=倒數(shù)第2位......第N位=倒數(shù)第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最長回文子串怎么實現(xiàn)”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對Java最長回文子串怎么實現(xiàn)這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
