Java最长回文子串怎么实现

这篇文章主要讲解了“Java最长回文子串怎么实现”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“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最长回文子串怎么实现这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！