算法简介

Manacher 算法用于求解一串字符串中的最长回文子串的长度。

如：abab 的最长回文子串的长度为3。

时间复杂度

$ O(n) $

实现原理

1.构造

回文串有两种情况：

情况1：abba，其对称轴在两字符中间
情况2：abcba，其对称轴在中间字符上

由于 Manacher 算法只能处理第二种情况，所以要对给定字符串进行重新构造，构造方法如下：

例：对字符串 abbcac 进行构造

1.首先在字符串首段和末端添加开始符和结束符，一般用'$'和'^'表示。
2.对于每个字符，保证其左右两侧分别有一个'#'。

那么原字符串就变为 $#a#b#b#c#a#c#^，其任意回文子串都满足情况2

2. 算法思想

设数组 p[i]：以字符 a[i] 为中心的最大的回文串的半径长度。

处理步骤为从前向后枚举，过程中不断维护右边界最靠右的回文串。

其中 mid 为回文串对称轴位置，maxright（后简称为 mr ）为最右边界。

对于遍历到的某个 a[i] 可以分为三种情况

① i 在内部且对称点回文串在内部

j 为以 mid 为对称轴的 i 的对称点，由于该区间内的字符串都是以 mid 为中心对称的，所以红色标注的区域也是对称的。

那么此时有 p[i] = p[j]。

② i 在内部且对称点回文串在外部

这里可得 i 的右侧边界一定等于 mr。

因为若超出的话，i 的红色区域右侧画斜杠部分与左侧部分对称，则与 j 的斜杠部分相同，则白色区域部分并不是以 mid 为中心的，边界最靠右的回文子串，所以 p[i] 最大只能到 mr 。

③ i 在外部

在外部则重新开始计算，令 p[i] = 1，然后不断对比求出 p[i]。

算法代码

const int N = 2e7+10;

int p[N];
char a[N],b[N];

// n 为题目给出的原字符串
int manacher(int n) {
    int k = 0;
    b[k ++ ] = '$',b[k ++ ] = '#';
    
    for (int i = 0 ; i < n ; i ++ ) b[k ++ ] = a[i], b[k ++ ] = '#';
    
    b[k ++ ] = '^';
    
    int mid,mr = 0;
    for (int i = 1 ; i < k ; i ++ ) {
        if(i < mr) p[i] = min(p[2 * mid - i] , mr - i);
        else p[i] = 1;
        
        while(b[i + p[i]] == b[i - p[i]]) p[i] ++ ;
        
        if(i + p[i] > mr) {
            mr = i + p[i];
            mid = i;
        }
    }
    
    int ans = 0;
    for (int i = 0 ; i < k ; i ++ ) ans = max(ans,p[i]);
    
    return ans - 1;
}

参考

[1] Acwing算法进阶课