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

题目

Leetcode647 $\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;
    }
};