manacher（马拉车）算法

时间复杂度
求解一个字符串的最长回文子串长度的问题。
注：先插入 n+1 个 # ，再设置一个 po，维护已知区域 (po-Next[po]，po+Next[po])，即维护 po。

char s[maxn], t[maxn<<1];  // s 为文本串 t 为加 # 串
int Next[maxn<<1]; // t 中以 i 为中心的最长回文半径

int manacher(char s[]) {
    int n = strlen(s+1);
    for(int i = 1; i <= n+1; ++ i) {
        t[(i<<1)-1] = '#';
        t[(i<<1)] = s[i];
    }
    int po = 1, ans = 0;
    Next[po] = 1;
    for(int i = 2; i <= (n<<1|1); ++ i) {
        if (Next[(po<<1)-i] + i < Next[po] + po) Next[i] = Next[(po<<1)-i];
        else { // 已知区间全部匹配
            int j = (Next[po] + po <= i) ? 1 : Next[po] + po - i; // i 不在已知区域 j 为 1
            while(t[i+j] && t[i-j] && t[i+j] == t[i-j]) ++j;
            Next[po=i] = j;
        }
        ans = max(Next[i]-1, ans);
    }
    return ans;
}

带权回文串（exkmp）

char s[maxn], t[maxn<<1];  // s 为文本串 t 为加 # 串
int Next[maxn<<1]; // t 中以 i 为中心的最长回文半径
int a[27];      // 不同字母有不同点值
int p[maxn<<1]; // 回文串的权值
int pre[maxn];  // 前缀回文串权值
int suf[maxn];  // 后缀回文串权值

void manacher(char s[]) {
    int n = strlen(s+1);
    for(int i = 1; i <= n+1; ++ i) {
        if (i <= n) pre[i] = suf[i] = 0; // 初始化
        t[(i<<1)-1] = 'a'-1;
        t[(i<<1)] = s[i];
    }
    int po, pw = 0, l = 0, r = n+1<<1;
    Next[po=l+1] = 1;
    for(int i = l+2; i < r-1; ++ i) {  // 第一个和最后一个 # 不需要判断
        pw +=  a[t[i]-'a'+1] * 2;
        if (Next[(po<<1)-i] + i < Next[po] + po) Next[i] = Next[(po<<1)-i], p[i] = p[(po<<1)-i];
        else { // 已知区间全部匹配
            int j = (po + Next[po] <= i) ? 1 : Next[po] + po - i;
            p[i] = (po + Next[po] <= i ? 0 : p[po] - pw) +  (pw = a[t[i]-'a'+1]); // 回文串的权值
            while(i-j>l && i+j<r && t[i+j] == t[i-j]) p[i] += 2*a[t[i+j]-'a'+1], ++j;
            Next[po=i] = j;
        }
        if (i - Next[i] == l) pre[  Next[i]-1] = p[i]; // 前缀回文串权值
        if (i + Next[i] == r) suf[n-Next[i]+2] = p[i]; // 后缀回文串权值
    }
}