【小白爬Leetcode647】回文子串 Palindromic Substrings

• 題目
• Manacher算法 O(n)

題目

Leetcode647 m e d i u m \color{#FF4500}{medium} medium

點選進入原題連結：回文子串 Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Manacher算法 O(n)

Manacher算法是用來求最長回文子串的，為何能用來統計回文子串的數量呢？這裡官方解答一帶而過，我比較愚笨，覺得有必要記錄下原因。

例如奇數個字元的回文子串：

以c為中心的一個最長回文子串為

#a#d#c#d#a#

，那麼以c為中心，我可以構造出

adcda

，

dcd

，

c

這三個回文子串，是以

#a#d#c#d#a#

實際上包含了3個回文子串。而根據Manacher算法的規則，c的回文半徑P=5（回文半徑從0開始算，即不算回文中心本身）。

再例如偶數個字元的回文子串：

以#為中心的一個最長回文子串為

#a#a#

，那麼以#為中心，我可以構造出

aa

這一個回文子串，而根據Manacher算法的規則，#的回文半徑P=2。

綜上，我們可以得到一個映射關系：字元

i

可以産生的回文子串的數量為：

(P[i]+1)/2

。

那麼這道題首先用Manacher算法算出P，再周遊去，按照

(P[i]+1)/2

的規則累加即可得到答案。

class Solution {
public:
    int countSubstrings(string s) {
        //Preprocess the string
        string T = "^";
        for(const char c:s){
            T += '#';
            T += c ;
        }
        T+="#!";
        int n = T.size();
        //建構P[i]
        vector<int> P(n,0); //回文半徑從0開始算，那麼回文子串的長度為P[i]
        int C = 0; //中心
        int R = 0; //回文字串右邊界
        for(int i=0;i<n;i++){
            //可以用對稱性的情況
            if(i<R){
                int i_mirror = 2*C-i; //對稱點
                P[i] = min(P[i_mirror],R-i);
            }
            //中心拓展來補充對稱性cover不到的地方
            while(i-P[i]-1>=0 && i+P[i]+1<n && T[i-P[i]-1]==T[i+P[i]+1]) ++P[i];
            //更新C和R
            if(i+P[i] > R){ //若是超出了右邊界
                C = i;
                R = i + P[i];
            }
        }
        //根據P[i]來計算回文子串的數量
        int ans = 0;
        for(int num : P){
            ans += (num+1)/2; //P[i]和可構成的回文子串之間的關系
        }
        return ans;
    }
};