题解 | #最长回文子串#

Manacher算法，O(n)。思路写在注释里了。
可能有有同学好奇为啥是O(N)的。太麻烦没自己证明，不过可以粗略体会下：
for循环毫无疑问是O(n)的，问题在于“统计未知部分”这里的while循环不好估计。
已知是统计未知部分时起始位置
由，
得，
则，
而更新时i-ans[i]<=best-ans[best]

class Solution {
public:
    /*
        Manacher算法
    */
    int getLongestPalindrome(string A, int n) {
        //加间隔符统一奇数、偶数长度的回文串，方便处理
        // 例子：cbc  --> #c#b#c#
        n=A.size()*2+1;
        char S[n+1];S[n-1]='#';S[n]=0;
        for (auto i=0;i<A.size();++i) {S[i*2]='#';S[i*2+1]=A[i];} 
        //printf("%s\n",S);
        int ans[n];ans[0]=1;// 以S[i]为起点的回文串半径
        int best=0;// 包含S[i]的、左端点最靠左的回文串
        int result=0;
        for (int i=1;i<n;++i)
        {
            ans[i]=1;
            auto j=best-(i-best);//在best回文串中i的镜像位置
            //在best镜像范围内j与i等价，直接复用之前的计算结果
            if (j<i)  ans[i]=max(ans[i],  min(ans[j],ans[best]-(best-j))    );
            //统计未知部分
            while (0<=i-ans[i]  && i+ans[i]<n && S[i-ans[i]]==S[i+ans[i]] )
                ++ans[i];
            //更新best
            if (   best+ans[best]<=i //best覆盖不了i 
                || i-ans[i]<=best-ans[best] //i的左端点更靠左
            )
                best=i;
            //统计result
            result=max(result,ans[i]-1);
        }
        return result;

    }
};