最簡便的找字元串中最長迴文子串的方法是什麼？

01-04

我是一個剛學java沒多久的新手，最近碰到一道題是求一個字元串里最長和最短的迴文是什麼（不考慮大小寫，沒有空格）我用的方法是創造多個array，一層層篩選，但我覺得很冗長而且麻煩，我上網查過有叫Manacher"s algorithm的方法並不是很懂，想請教一下各位有沒有更簡便更完美的演算法，謝謝。
代碼貼在回答區一樓了。

暴力遍歷所有子串，複雜度O(n^3)

要最簡便，最無腦肯定是暴力解法，就是遍歷字元串的「所有子串」，並判斷每個子串是否為對稱迴文。因為字元串所有子串的複雜度為`O(n^2)`，再判斷迴文，總體複雜度達到`O(n^3)`。

可以簡單做一些優化，

從最長的子串開始遍歷，一旦找到一個迴文，就終止迭代。
判斷迴文採用收縮法。從最外一對字元往中心推進。

代碼在此，

public class Solution { public String longestPalindrome(String s) { for (int size = s.length(); size &> 0; size--) { for (int low = 0, high = low+size-1; high &< s.length(); low++, high++) { if (shrinkCheckPalindrome(s,low,high)) { return s.substring(low,high+1); } } } return s.substring(0,1); } public boolean shrinkCheckPalindrome(String s, int low, int high) { while (low &<= high) { if (s.charAt(low) == s.charAt(high)) { low++; high--; } else { return false; } } return true; } }

實際運行的複雜度是沒有`O(n^3)`這麼恐怖。Leetcode將將通過。

從中心點向外擴散，複雜度O(n^2)

迴文就是中心對稱的單詞。從字元的中心開始，向兩邊擴散檢查迴文。這需要維護一個指針，從頭開始，以每一個位置為中心遍歷一遍。這比暴力遍歷所有子串省了很多重複判斷。以某個字元為核心一旦探測到邊界，更長的的串就都不再考慮。複雜度O(n^2)。注意，迴文需要同時檢查單核`aba`以及雙核`abba`的情況。

代碼如下，

public class Solution { private int max = 0; private String res = ""; public String longestPalindrome(String s) { if (s.length() == 1) { return s; } for (int i = 0; i &< s.length()-1; i++) { checkPalindromeExpand(s,i,i); checkPalindromeExpand(s,i,i+1); } return res; } public void checkPalindromeExpand(String s, int low, int high) { while (low &>= 0 high &< s.length()) { if (s.charAt(low) == s.charAt(high)) { if (high - low + 1 &> max) { max = high - low + 1; res = s.substring(low,high+1); } low--; high++; } else { return; } } } }

結果比剛才的暴力解法快了不少，leetcode上40ms

Manacher演算法，複雜度O(n)

Manacher演算法才是計算最長迴文子串的最理想方法。實際上中心點擴散法還是有一些字元是重複判斷了。Manacher演算法正是在剛才的中心點擴散法的基礎上，做了優化，跳過了某些點的判斷工作，因為根據之前判斷過的內容，可以推斷出後面字元的對稱情況。

Manacher演算法的具體細節，參見我的這篇帖子：《Hello SHEN》。這裡不展開。

Manacher 代碼如下，這是Sedgewick官方的版本，

public class Solution { private int[] p; private String s; private char[] t;


    public String longestPalindrome(String str) {

        s = str;

        preprocess();

        p = new int[t.length];

        int mid = 0, right = 0;

        for (int i = 1; i &< t.length-1; i++) {
            int mirror = 2*mid - i;
            if (right &> i)

                p[i] = Math.min(right - i, p[mirror]);

            while (t[i + (1 + p[i])] == t[i - (1 + p[i])])

                p[i]++;

            if (i + p[i] &> right) {

                mid = i;

                right = i + p[i];

            }

        }
        int length = 0;

        int center = 0;

        for (int i = 1; i &< p.length-1; i++) {
            if (p[i] &> length) {

                length = p[i];

                center = i;

            }

        }

        return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2);

    }

private void preprocess() { t = new char[s.length()*2 + 3]; t[0] = "$"; t[s.length()*2 + 2] = "@"; for (int i = 0; i &< s.length(); i++) { t[2*i + 1] = "#"; t[2*i + 2] = s.charAt(i); } t[s.length()*2 + 1] = "#"; } }

leetcode上25ms，好像還不是最快的。。。

我記得一道類似的題。

先倒序複製一個。

然後kmp找公共欄位……

大概這個思路，歡迎神犇說細節。

我提供一個思路吧。

我們考慮一下迴文串的結構，正著看和反著看都是一樣的，那麼，容易作出以下斷言：

如果一個串 S 中存在最大迴文子串 s，那麼該串的逆串 S" 必定能找到一子串 s"，使得 s == s" 成立。

然後就可以把這個問題轉化為求兩個串中的最大公共子串的問題。然後就有很多優化演算法可以我們了。這類問題的典型解法就是 DP。

樓上其他朋友提到的 KMP 也是效率非常好的。考慮 KMP 的演算法下，所需要的空間是存放逆串和失配向量的兩個數組，空間複雜度是 2n。翻轉字元串需要掃描一遍原串，找到最大公共子串也需要掃描一遍。所以時間複雜度也是 2n。

從如何確定一個子串是否是迴文串開始，我們需要知道這樣的 pair（中心，半徑）。意思是從每個中心點最多可以向左或者向右擴展的半徑。因為迴文串長度可能是奇數或偶數，可以用一種技巧來消除這種特判，在相鄰字元中間插入一個特殊字元（如『#』）。

例如，「12212321" =&> "#1#2#2#1#2#3#2#1#"，如果令 P[i] 為以第 i 個字元為中心的擴展半徑，你會發現其對應的最長迴文串的長度就是 P[i] - 1。

S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
(p.s. 可以看出，P[i]-1正好是原字元串中迴文串的總長度）

（參考自：O(n)時間求字元串的最長迴文子串 - Felix021 - 將所有歡脫傾翻O(n)時間求字元串的最長迴文子串 - Felix021 - 將所有歡脫傾翻）

所以就歸結到如何求 P 數組的問題。為了節約輪子成本，求解過程請參考上述鏈接。

這就是馬拉車演算法啊！

https://github.com/githubwoniu/learnprogram/blob/master/leetcode/05/note_bajdcc.md

簡單思路

從左往右找迴文串，最後給個最長的。

簡單方法不簡單。。怎麼找迴文串是個問題，從邊上往中間找肯定不行，迴文串的特點是兩邊對稱，所以應該從對稱方面著手。

本來為了避免數組越界以及單核/雙核問題，需要每兩相鄰位間插入一個@來解決，不過這樣可能會提高運行時間。。不過想了想，我沒用這種方法。

優化思路

首先，一個迴文串的字元頻度應該是：中點頻度最低為1，其他字元頻度最低為2。

那麼，如果串中有頻度是1的字元，它肯定位於迴文串的中心，不然就不屬於任何迴文串。

因此，按頻度可以篩選掉一定量的多餘字元，將母串進行分割。分割的好處是子串有界。

最懶方法：遍歷整串，從中心向兩側擴張並做比較，取得長度，最後返回最大長度所在的串。

優化：

在遍歷整串過程中，最大長度maxlen會時刻增加，那麼，當分割後的有界子串長度小於最大長度maxlen時，就不需要再去判斷了。
如果串的某個連續子串(len&>=2)它們的頻度都是1，那麼它們就不屬於任何迴文串，可以快速剔除，節省時間。這是關鍵。
其他方法還沒想到，歡迎補充。

所以大體的思路是：

統計字元頻度，用數組表示頻數
找出頻度為1的字元a，看以a為單核中心向外擴散，求最長迴文；如果沒有迴文，就將它從串中斷開，進行分治；如果迴文長度超過記錄，就保存它
然後從左到右查迴文，只有長度超過記錄，才保存
第一次串分割完畢後，進行分治，重新統計頻度，回到1步驟

運行時間

time=9ms https://leetcode.com/submissions/detail/87484290/

代碼（回來寫注釋）

class Solution { int count[256];

public: string longestPalindrome(string str) { int start = 0, end = str.length() - 1; if (longestPalindrome(str.c_str(), start, end) &> 1) {//這裡改了下 return str.substr(start, end - start + 1); } else { return str.substr(0, end &< start ? 0 : 1); } } int longestPalindromePartition(const char *str, int start, int end, int maxLen) { if (end - start + 1 &<= maxLen) return 1; int maxStart, maxEnd, len = maxLen; int reserve = (maxLen + 1) / 2; int reserveEnd = end - reserve + 1; for (int i = start + reserve - 1, j, k; i &<= reserveEnd; ++i) { if (str[i] == str[i + 1]) { for (j = i + 1, k = 1; i - k &>= start j + k &<= end; ++k) { if (str[i - k] != str[j + k]) break; } k--; if (j - i + 1 + k * 2 &> len) { len = j - i + 1 + k * 2; reserve = (len + 1) / 2; reserveEnd = end - reserve + 1; maxStart = i - k; maxEnd = j + k; } } for (j = reserve; j &> 0; --j) { if (str[i - j] != str[i + j]) break; } if (j == 0) { for (j = reserve + 1; i - j &>= start i + j &<= end; ++j) { if (str[i - j] != str[i + j]) break; } reserve = --j; reserveEnd = end - reserve; if (j * 2 + 1 &> len) { len = j * 2 + 1; maxStart = i - j; maxEnd = i + j; } } } if (maxLen &< len) { start = maxStart; end = maxEnd; return len; } return 1; } int longestPalindrome(const char *str, int start, int end) { if (start == end) return 1; for (int i = 0; i &<= 26; ++i) { count["a" + i] = 0; } int len = end - start + 1; for (int i = start; i &<= end; ++i) { count[str[i]]++; } auto dups = new int[len]; int dupCount = 0; for (int i = start; i &<= end; ++i) { dups[i] = count[str[i]] &> 1 ? (dupCount++, 1) : 0; if (dups[i] == len) return len; } int tmpStart = -1, tmpEnd = -1, maxStart = -1, maxEnd = -1, tmpLen, maxLen = 1; for (int i = start; i &<= end; ++i) { if (dups[i]) { tmpStart = i++; for (; i &<= end; ++i) { if (!dups[i]) { tmpEnd = i - 1; break; } } if (i-- &> end) { tmpEnd = end; } if ((tmpLen = longestPalindromePartition(str, tmpStart, tmpEnd, maxLen)) &> maxLen) { maxLen = tmpLen; maxStart = tmpStart; maxEnd = tmpEnd; } } else { tmpStart = i; for (; i &<= end; ++i) { if (dups[i]) { tmpEnd = i - 1; break; } } if (i-- &> end) { tmpEnd = end; } if (tmpStart == tmpEnd) { while (tmpStart &>= start tmpEnd &<= end str[--tmpStart] == str[++tmpEnd]); tmpLen = (--tmpEnd) - (++tmpStart) + 1; if (tmpLen &> maxLen) { maxLen = tmpLen; maxStart = tmpStart; maxEnd = tmpEnd; } } } } start = maxStart; end = maxEnd; delete[]dups; return maxLen; } };

順便給小馬哥打個廣告，歡迎加入c++水群。。

沒有，最好的就是馬拉車了。當然的你的簡便是偏向於簡單還是速度呢？如果是簡單自然暴力最好。

manacher好用呀

考慮你當前找到最長的子串是以i為中心 long【i】為長度那麼點j（小於i+longi）的最長子序列一定大於等於long（2i-j）因為2i-j和j關於i對稱它們兩邊的也是對稱的但如果j+這個long出了i+longi 就不能保證和j左邊對稱了因為出了管轄範圍所以比較一下取小一點的值..這樣對於每個點都有個基礎對稱值這個值是之前的範圍內然後再往外擴相當於每個點都只走了一次～複雜度On完美...然後記得如果哪一個longj比longi還長了那就更新一下～還有一點就是沒兩個字元中間都加一個沒出現的字元這樣不用判斷奇偶～還直接long那個算出來不用*2+1什麼的了

恩大概就是這樣..

突然想起有一次互測的時候學弟找的一個暴力演算法，比馬拉車還快，而且賊短…

下面很醜的代碼就是找最長迴文子串長度，100W數據500ms出。

#include & #include & #include & char str[1000002 + 1200];


int fast(char *p) {

    int ans = 1;

    for (int i = 1; p[i]; ++i) {

        int s = i, e = i, t;

        while (p[e + 1] == p[i]) ++e;

        i = e;

        while (p[s - 1] == p[e + 1]) --s, ++e;

        if ((t = e - s + 1) &> ans) ans = t;

    }

    return ans;

}

int main() { str[0]="$"; while (scanf("%s", str + 1) != EOF) { printf("%d ",fast(str)); } return 0; }

可以大力後綴自動機（笑）

正經點的話你可以用迴文樹啊

大概就是一個類似kmp的構造過程，還是挺簡單易懂的

懶得深入寫了，如果想知道細節的話去找找吧

其實哈希也是可以做的，比manacher好理解一些

brute-force 演算法.

naive algorithm.

這是我第一次看到暴力法的官方名字...

---

其實manacher也不是很難寫嘛..