leetcode 刷題 回文子串（647）

leetcode 刷題 回文子串（647）

其他類似的求最長回文子串，也是同樣的思路

int dp[1001][1001];//dp[i][j]表示從i到j的子字元串是否為回文，若是為1
    int countSubstrings(string s) {
        int n=s.size();
        int ans=0;
        for(int i=0;i<n;i++)//預處理子字元串長度為1，為2的
        {
            dp[i][i]=1;
            ans++;
            if(i<n-1)
            {
                if(s[i]==s[i+1])
                {
                        dp[i][i+1]=1;
                        ans++;
                }
            }
        }
        for(int L=3;L<=n;L++)//從字元串長度為3開始枚舉
        {
            for(int i=0;i+L-1<n;i++)//枚舉左端點
            {
                int  j=i+L-1;//計算右端點
                if(s[i]==s[j]&&dp[i+1][j-1]==1)//狀态轉移方程
                {
                        dp[i][j]=1;
                        ans++;
                }

            }
        }
        return ans;
        

    }
           

還有Manacher 算法

在所有的相鄰字元中間插入 #，比如 abaa 會被處理成 #a#b#a#a#，這樣可以保證所有找到的回文串都是奇數長度的。

用 f(i)來表示以 s的第 i位為回文中心，可以拓展出的最大回文半徑，那麼 f(i) - 1就是以 i 為中心的最大回文串長度 。

假設我們已經計算好了 [1, i - 1]區間内所有點的 f（即[1,i−1] 這些點作為回文中心時候的最大半徑）， 那麼我們也就知道了 [1, i - 1]拓展出的回文達到最大半徑時的回文右端點。例如 i=4 的時候 f(i) = 5，說明以第 4 個元素為回文中心，最大能拓展到的回文半徑是 5，此時右端點為 4 + 5 - 1 = 8。是以當我們知道一個 i對應的 f(i)的時候，我們就可以很容易得到它的右端點為 i + f(i) - 1。

Manacher 算法如何通過已經計算出的狀态來更新 f(i) 呢？Manacher 算法要求我們維護「目前最大的回文的右端點 r_m 」以及這個回文右端點對應的回文中心 i_m。我們需要順序周遊 s，假設目前周遊的下标為 i。我們知道在求解 f(i)之前我們應當已經得到了從 [1, i - 1]所有的 f，并且目前已經有了一個最大回文右端點 r_m以及它對應的回文中心 i_m。

初始化 f(i)

如果 i<r_m ，說明 i被包含在目前最大回文子串内，假設 j是 i關于這個最大回文的回文中心 i_m的對稱位置（即 j + i = 2×i_m），我們可以得到 f(i)至少等于 min{f(j), r_m - i + 1}。這裡将 f(j)和 r_m - i + 1取小，是先要保證這個回文串在目前最大回文串内。（思考：為什麼 f(j)f(j) 有可能大于 r_m - i + 1？）

如果 i > r_m,那就先初始化 f(i) = 1。

中心拓展

做完初始化之後，我們可以保證此時的 s[i + f(i) - 1] = s[i - f(i) + 1]，要繼續拓展這個區間，我們就要繼續判斷 s[i + f(i)]和 s[i - f(i)]是否相等，如果相等将 f(i) 自增；這樣循環直到 s[i + f(i)] 不等于s[i - f(i)]，以此類推。我們可以看出循環每次結束時都能保證 s[i + f(i) - 1] = s[i - f(i) + 1]，而循環繼續（即可拓展的條件）一定是 s[i + f(i)] = s[i - f(i)]。 這個時候我們需要注意的是不能讓下标越界，有一個很簡單的辦法，就是在開頭加一個 $，并在結尾加一個 !，這樣開頭和結尾的兩個字元一定不相等，循環就可以在這裡終止。

這樣我們可以得到 ss所有點為中心的最大回文半徑，也就能夠得到 S 中所有可能的回文中心的的最大回文半徑，把它們累加就可以得到答案。

 代碼如下：

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        string t = "$#";
        for (const char &c: s) {
            t += c;
            t += '#';
        }
        n = t.size();
        t += '!';

        auto f = vector <int> (n);
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            // 初始化 f[i]
            f[i] = (i <= rMax) ? min(rMax - i + 1, f[2 * iMax - i]) : 1;
            // 中心拓展
            while (t[i + f[i]] == t[i - f[i]]) ++f[i];
            // 動态維護 iMax 和 rMax
            if (i + f[i] - 1 > rMax) {
                iMax = i;
                rMax = i + f[i] - 1;
            }
            // 統計答案, 目前貢獻為 (f[i] - 1) / 2 上取整
            ans += (f[i] / 2);
        }

        return ans;
    }
};

作者：LeetCode-Solution
連結：https://leetcode-cn.com/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。