更高效的回文串算法——Manacher algorithm

——以“最长回文子串”及“回文子串个数”为例

首先明确，这两题使用动态规划均能求解，不过复杂度还是相对较高

这里先给出动态规划的状态转移方程，有兴趣的读者不妨一试

$dp[i][j]$表示字符串中从$i$到$j$的子串是否为回文串

\begin{equation}
\label{q1}
dp[i][j]=\left\{
\begin{aligned}
1 & ,&\ a[i]=a[j] \& (dp[i+1][j-1]=1 | j-i<=2)\ \\
0 & , &else
\end{aligned}
\right.
\end{equation}

但是用dp来做的话，总的时间复杂度还是趋近于$n^2$只能是起到了常数级别的优化。于是便引出了我们今天的主角

1975年，芝加哥大学伊利诺斯分校的一名讲师—— Glenn K Manacher在acm期刊上独自发表了A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a String一时间引起轰动，而这个算法也得以被命名为Manacher algorithm

而Manacher在国语当中音近同“马拉车”，这个算法也被形象的称为马拉车算法。

其实按我个人的理解马拉车这个行为在算法过程中还是略有体现的，就请继续向下看吧

以这样一组数据为例

相必可以一眼看出最长的回文串是这个部分

我们在处理回文串的时候可以注意到一点，任何回文串的中心对称位置是具有特殊性质的，回文串的中心位置有两种

显然这两种情况需要得到统一，将偶数长度的回文串通过无关元素的扩增就可以实现其统一为奇数元素，而这也是Manacher algorithm的关键的预处理

我们可以通过选取"#"作为一个无关元素来填充到字符之间，需要保证的是这样一个元素必须在字符串之内没有出现过。

扩增之后如图，至于这个"&"和"$"则是用来终止判断循环，以确保不会越界

下面就开始具体的说一说manacher algorithm。

他的算法中有三个核心部分，一个是p[]数组， p[i] 用来记录以i为中心的最长回文子串半径，我们的目标也就是得出这样的一个数组即可，其中的最大值-1（因为最外周又辅助元素"#"需要剔除掉）就是最长回文子串的长度。

第二个就是mid变量，用来标记我目前已经找到的回文子串的中心，这个的意义在于：一个已知的长回文子串，如果其中左半部分有一个回文子串的话，其右半部分的对应位置必定也有一个回文子串，而且只长不短（长是因为其向右端还可能继续延伸而左端的回文子串已经得到了固定）。

第三个就是mx变量，用来记录我现在已经扫到的右端点。

在遍历过程中就是通过mid与mx不断得到更新（右延）的过程来实现p[]数组的运算

读者不妨看（看不清的读者可以右键——在新标签页中打开图片）

以上便是manacher algorithm的具体演示。

下面我们来看代码的实现

Description

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.

Input

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度$len <= 110000$

Output

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Accepted Code

/*
 * @Author: Gehrychiang
 * @Date: 2020-02-21 00:18:50
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#include <******>
using namespace std;
const int maxn = 3e5;
char ori[maxn];
char str[maxn];
int len_ori, len_str;
int p[maxn];
void manacher()
{
    int mid = 0;                      //当前中心处
    int mx = 0;                       //右端
    for (int i = 0; i < len_str; i++) //目的给出p[i]也就是以i为中心的最长回文串的长度
    {
        if (mx > i) //没有越过右端的时候
        {
            p[i] = min(p[2 * mid - i], mx - i); //此时将p[i]关于mid的镜像位置的值与p[i]到右端作比较
            //更好的理解是我的i到mx肯定是能到的但是不一定就够了，我只是暂时存到我已知的位置
        }
        else
        {
            p[i] = 1; //否则他至少有本身自己这么长
        }
        //以上其实就是马拉车算法他保留了之前的结果从而优化掉接下来无谓运算的过程，每一对回文字符实际上只需要匹配一次即可
        while (str[i + p[i]] == str[i - p[i]]) //以当前i去做暴力匹配
        {
            p[i]++;
        }
        if (i + p[i] >= mx) //如果此时扫完了发现可以有更大的，那就需要更新右端点的位置以及中心点
        {
            mx = i + p[i];
            mid = i;
        }
    }
}
//这个算法的本质是如果已经有发现了长回文，那么包含在长回文中的左边的短回文在右边肯定也是短回文。
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    while (~scanf("%s", ori))
    {
        len_ori = strlen(ori);
        len_str = 2;
        //head 和 tail用来保证寻找最长循环子串的时候一定可以停下来(也就是一个临界的判出条件)
        str[0] = '&'; //head
        str[1] = '#'; //mid
        for (int i = 0; ori[i]; i++)
        {
            str[len_str] = ori[i];
            str[len_str + 1] = '#';
            len_str += 2;
        }
        str[len_str] = '*'; //tail
        manacher();
        int ans = 0;
        int lmark = 0;
        for (int i = 0; i < len_str; i++)
        {
            if (ans < p[i])
            {
                ans = p[i];
                lmark = i;
            }
        }
        cout << ans - 1 << endl; //左右还有多出来的'#'
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

至于另一题也只是用上了p[]数组而已，核心算法大同小异，水题在此不表，如有需要可在评论区留言