補(bǔ)齊字符串使其成為回文字符串

給定一個(gè)字符串str，只能在str的后面添加字符，想讓str整體變成回文串，返回至少要添加幾個(gè)字符

Manacher 算法

首先介紹下manacher 算法：
Manacher 算法是一種線性時(shí)間復(fù)雜度的求解最長回文子串的算法。它的核心思想是利用已知回文信息，避免重復(fù)計(jì)算。 Manacher 算法的基本思想是通過預(yù)處理得到一個(gè)包含原字符串所有回文子串的數(shù)組，然后對(duì)于每個(gè)字符，如果它是回文中心，則將它的位置加倍，否則不做任何修改。最后返回?cái)?shù)組中最大的值即可 。具體可以看下上期manacher算法。
Manacher算法 – 回文長度算法
可以先看上期的回文字符串的算法，這個(gè)可以在時(shí)間復(fù)雜度為O(n)的情況下，計(jì)算出最長回文子串的長度。

在這個(gè)題中，我們只需要找到第一次半徑到字符串末尾的字符位置，然后補(bǔ)齊前面到半徑位置的字符，就是需要的最短的字符串。
舉個(gè)例子：
123abcbabc 在這個(gè)字符串中,用manacher 算法中，找到第一次回文半徑到字符末尾的位置字符，也就是倒數(shù)一個(gè)a的位置，然后補(bǔ)齊以a為只心的回文字符前面的字符，也就是ba321.使其整體成為回文字符串。

代碼演示

/**
     * 補(bǔ)齊字符串。
     * @param s
     * @return
     */
    public static String shortestEnd(String s) {
        //只有一個(gè)字符串時(shí)，不需要補(bǔ)
        if (s == null || s.length() < 2){
            return null;
        }

        char[] chars = manacherString(s);
        int[] pArr = new int[chars.length];
        int C = 0;
        int R = 0;
        int maxContainsEnd = -1;

        for (int i = 0;i < chars.length;i++){
            pArr[i] = R > i ? Math.min(pArr[2 * C - i],R - i) : 1;

            while (i + pArr[i] < chars.length && i - pArr[i] > -1){
                if (chars[i + pArr[i]] == chars[i - pArr[i]]){
                    pArr[i]++;
                }else {
                    break;
                }
            }
            if (i + pArr[i] > R){
                R = i + pArr[i];
                C = i;
            }
            if (R == chars.length){
                maxContainsEnd = pArr[i];
                break;
            }
        }

        char[] ans = new char[s.length() - maxContainsEnd + 1];
        for (int i = 0; i < ans.length;i++){
            ans[ans.length - i -1] = chars[i * 2 + 1];
        }
        return new String(ans);
    }


        /**
         * 處理字符串
         * @param s
         * @return
         */
    public static char[] manacherString(String s){
        char[] chars = s.toCharArray();
        char[] res = new char[chars.length * 2 + 1];
        int index = 0;
        for (int i = 0; i < res.length;i++){
            res[i] = (i & 1) == 0 ? '#' : chars[index++];
        }
        return res;
    }

Manacher 算法

Manacher算法 – 回文長度算法文章來源地址http://www.zghlxwxcb.cn/news/detail-564446.html

到了這里，關(guān)于字符串后面補(bǔ)最短長度的字符，使其整體成回文字符串(java)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！