计算最长回文子串Manacher

马拉车

复杂度：O(n)

计算最长回文子串的暴力方法

i 从头开始遍历，每次都以 i 为中心向外扩展

弊端：不适用于偶数回文，且复杂度为O(n^2^)

Manacher

Manacher算法详解 - BT-7274 - 博客园 (cnblogs.com)

int Manacher(string s)
{
	if(s.length() == 0) return 0;
    int len = (int)(s.length()*2-1);
    char *cArry = new char[len];
    int *pArry = new int[len];
    //预处理：全都变成奇数回文串
    for(int i = 0; i < len; i++)
        cArry[i] = i&1 ? s[(i-1)/2] : '#';
    //R:最右右边界  C：与R对应的回文中心 maxn：最大回文半径，返回值为maxn-1
    //R实际上是最右边界的右边一位
    int R = -1;
    int C = -1;
    int maxn = 0;
    for(int i = 0; i < len; i++)
    {
        pArry[i] = i > R ? 1 : min(R-i, pArry[2*C-i]); //取得可能的最短的回文半径 *R是最右边界的右边一位
        while(i+pArry[i] < len && i-pArry[i] > -1)   //暴力计算
        {
            if(cArry[i+pArry[i]] == cArry[i-pArry[i]]) pArry[i]++;
            else break;
        }
        //更新
        if(i+pArry[i] > R)
        {
            R = i+pArry[i];
            C = i;
		}
        maxn = maxn(pArry[i], maxn);
    }
    //清空动态数组
    delete[] cArry;
   	delete[] pArry;
    
    return maxn-1;
}

练习题

HDU 3068