最长回文子串 manacher algorithm

最长回文/对称子串 manacher algorithm
以下以字符串"abcdcbaabdcec"为例

LeetCode:longest palindromic substring

class Solution {
public:
    string longestPalindrome(string s) {
        string ts = "";
        for(size_t  i=0;i<s.size();++i) {ts += "#";ts += s[i];}
        ts += "#";

        int n = ts.size();
        vector<int> p(n,0);
        int R = 0,C = 0;
        int start = 0,length = 0;
        for(int i=0;i<n;++i){
            int j = 2*C - i;
            if(i<R && p[j]<R-i) p[i]=p[j];
            else if(i<R && p[j]>R-i) p[i] = R-i;
            else {
                int cnt = i<R?R+1:i+1;
                while(2*i-cnt >-1 && cnt < n && ts[cnt]==ts[2*i-cnt]) ++cnt;
                R = cnt-1;
                C = i;
                p[i] = R -i;
            }
            if(p[i]>length) {length = p[i];start = (i-p[i]+1)/2;}
        }
        return string(s,start,length);
    }
};