4.2.3　使用Manacher算法求最长回文子串

回文串（palindromic string）是指这个字符串无论从左读还是从右读，所读的字符顺序是一样的。给出一个字符串，要求计算出这一字符串的最长回文子串的长度。如果遍历每一个字符，并以该字符为中心向两边查找，则其时间复杂度为O(n²)。

Manacher算法，又被称为“马拉车”算法，可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串的长度。

由于回文分为偶回文（例如“bccb”）和奇回文（例如“bcacb”），而在处理奇偶问题上比较烦琐，例如，对于偶回文“bccb”，其对称中心是在两个“c”字符之间；对于奇回文“bcacb”，对称中心就是“a”字符。对此，Manacher算法在字符串首尾及各字符间各插入一个字符，而这个字符并未出现在字符串里。例如，字符串s是“abbahopxpo”，用未出现在字符串里的“#”字符插入，得到新字符串s_new是“$#a#b#b#a#h#o#p#x#p#o#”，其中，“$”为了防止越界。在字符串s中，有一个偶回文“abba”和一个奇回文“opxpo”，它们分别被转换为“#a#b#b#a#”和“#o#p#x#p#o#”，回文的长度都成了奇数。

对于给出新字符串s_new，定义一个辅助数组int p[]，其中p[i]表示以第i个字符为中心的最长回文的半径，如下所示：

所以，p[i]-1是原字符串中以该字符所在位置为中心的回文串的长度。

对于数组p，设置两个位置变量mx和id，其中mx表示以id为中心的最长回文的右边界，即mx=id+p[id]，如图4.2-4所示。

图　4.2-4

对于p[i]，如果i<mx，设j是i关于id的对称点，如图4.2-4所示，则基于以下三种情况可以求出p[i]的值：

1）以j为中心的回文串有一部分在以id为中心的回文串之外。因为mx是以id为中心的最长回文的右边界，所以以i为中心的回文串不可能会有字符在以id为中心的回文串之外；否则mx就不是以id为中心的最长回文的右边界。所以，在这种情况下，p[i]=mx–i。

2）以j为中心的回文串全部在以id为中心的回文串的内部，则p[i]=p[j]，而且p[i]不可能再增加。

3）以j为中心的回文串的左端正好与以id为中心的回文串的左端重合。则p[i]=p[j]或p[i]=mx–i，并且p[i]还有可能会继续增加，即while(s_new[i-p[i]]==s_new[i+p[i]])p[i]++；

所以，if(i<mx)p[i]=min(p[2*id-i],mx-i)；其中2*id-i为i关于id的对称点，即上面的j点，而p[j]表示以j为中心的最长回文半径，因此可以利用p[j]来快速求解p[i]。

【4.2.3.1　Palindrome】

Andy是一个计算机专业的学生，他正在上算法课，教授问学生一个简单的问题：“你们能不能提出一个有效的算法，来找出一个字符串中最长回文的长度？”

如果一个字符串向前读和向后读是相同的，则称其为回文，例如"madam"是回文，而"acm"则不是回文。

同学们认识到这是一个经典的问题，但是他们无法找到一个比遍历所有子串并检查它们是否是回文更好的解决方案，但显然这样的算法根本没有效率。过了一会儿，Andy举手说：“OK！我有一个更好的算法。”在Andy开始解释他的想法之前，停了一会儿，然后说：“好吧，我有一个更好的算法！”

如果你认为你知道Andy的最终解决方案，就证明它。给定一个最多1 000 000个字符的字符串，请查找并输出该字符串中最长回文的长度。

输入

你的程序将对最多达30个的测试用例进行测试，每个测试用例在一行中以最多1 000 000个小写字符的字符串形式给出。输入以字符串“END”开头的一行结束（为了清楚起见，用引号）。

输出

对于输入中的每个测试用例，输出测试用例编号和最长回文的长度。

试题来源：Seventh ACM Egyptian National Programming Contest

在线测试：POJ 3974

试题解析

本题直接使用Manacher算法求解。

设原串为str，长度为L，在原串的基础上产生辅助串str_new：str_new是在str的首尾及各字符间各插入一个字符“#”，str_new的首字符为“@”，尾字符为“$”；以第i个字符为中心的最长回文的半径为p[i]，初始时为0；以id为中心的最长回文的右边界为mx，即mx=id+p[id]，初始时为0；最长回文的半径为ans，初始时为0。

计算ans的方法如下。

枚举辅助串str_new的每一个字符位置i（1≤i≤2×L+1），尝试该位置作为中心位置：若mx在i的右侧（mx>i），则p[i]调整为min(mx-i,p[id×2-i])；否则调整为1。以i位置为中心计算最长回文的半径p[i]（for(;str_new[i-p[i]]==str_new[i+p[i]];p[i]++)）；若其右边界（p[i]+i）大于mx，则中心id调整为i，重新计算右边界mx（mx=p[i]+i,id=i;）；ans调整为max(ans,p[i])。

枚举完str_new的每一个字符位置后，ans-1即最长回文的半径。

参考程序

---

#include<iostream>
#define M 1000010
using namespace std;
char str[M],str_new[2*M];        //原串和辅助串
int p[2*M],len;                  //p[i]表示以第i个字符为中心的最长回文的半径，字符串长
                                 //度为len
void init()                      //构造辅助串
{
    len=strlen(str);             //计算字符串长度
    str_new[0]='@';              //辅助串的首字符
    str_new[1]='#';              //辅助串的间隔字符
    for(int i=0; i<len; i++)     //逐个字符地构造辅助串
    {
        str_new[i*2+2]=str[i];
        str_new[i*2+3]='#';
    }
    str_new[len*2+2]='$';        //辅助串的尾字符
}
void Manacher()                  //计算和输出最长回文的半径
{
    memset(p,0,sizeof(p));       //p[i]表示以第i个字符为中心的最长回文的半径，所有最长
                                 //回文的半径初始化为0
    int mx=0,di,ans=0;           //以id为中心的最长回文的右边界为mx，即mx=id+p[id]，
                                 //mx和最长回文的长度ans初始化为0
    for(int i=1; i<len*2+2; i++) //枚举每一个可能的中心字符
    {
        if(mx>i)                 //根据i位置在mx位置的左侧还是右侧，调整
                                 //最长回文半径的初始值
            p[i]=min(mx-i,p[di*2-i]);
        else
            p[i]=1;
        for(; str_new[i-p[i]]==str_new[i+p[i]]; p[i]++); //以i位置为中心计算最长回文//半径p[i]
        if(p[i]+i>mx)            //若以i为中心的右边界大于mx，则中心id调整为i，重新
                                 //计算右边界mx
            mx=p[i]+i,di=i;
        ans=max(ans,p[i]);       //调整最长回文的半径
    }
    printf("%d\n",--ans);        //输出最长回文的半径
}
int main()
{
    int t=1;                     //初始化测试用例编号
    while(~scanf("%s",str))      //反复输入字符串，直至输入“END”为止
    {
        if(!strcmp(str,"END")) break;
        printf("Case %d: ",t++); //输出测试用例编号
        init();                  //构造辅助串
        Manacher();              //计算和输出最长回文的半径
    }
}

---

【4.2.3.2　Best Reward】

经过一场艰苦的战斗，李将军取得了巨大的胜利。现在，国家元首决定用荣誉和财宝来奖励他所做的伟大贡献。

奖励李将军的一件财宝是一条由26种不同的宝石组成的项链，项链的长度为n，也就是n颗宝石串在一起构成了这条项链，而每颗宝石都属于26种宝石中的一种。

按照传统的观点，项链是有价值的当且仅当项链是回文——项链在任何方向上看起来都一样。然而，这个项链可能一开始还不是回文。所以国家元首决定把项链切成两半，然后把它们都交给李将军。

同一种类的所有宝石的价值是相同的（因为宝石的质量，宝石的价值可能是正的，也可能是负的；有些种类的宝石很漂亮，而有些宝石则看起来像普通的石头）。回文项链的价值等于宝石的价值之和，而不是回文的项链的价值为零。

现在的问题是，如何切割给出的项链使两个项链的价值之和最大，并输出这个值。

输入

输入的第一行是一个整数T（1≤T≤10），表示测试用例的数量。然后给出这些测试用例的描述。

对于每个测试用例，第一行是26个整数v₁,v₂,…,v₂₆（-100≤v_i≤100，1≤i≤26），表示每种宝石的价值。

每个测试用例的第二行是由字符“a”～“z”组成的字符串，表示项链，不同的字符表示不同的宝石，“a”的价值是v₁，“b”的价值是v₂，……，以此类推。字符串的长度不超过500 000。

输出

输出一个整数，它是李将军可以从这串项链中获得的最大值。

试题来源：2010 ACM-ICPC Multi-University Training Contest（18）—Host by TJU

在线测试：HDOJ 3613

试题解析

本题题意：对于字母表中的26个字母，每个字母都有一个价值。给出一个由字母组成的字符串，将该字符串切成两份，对于每一份，如果是回文串，就计算该子串的所有字符的价值之和，否则该子串的价值为0。请求出将字符串切成两份后能够获得的最大价值。

本题求解步骤如下：首先，用Manacher算法求出以每个字符为中心的回文串的长度；然后，枚举切割点，得到两个子串，由此确定每个子串的中心点；检查以该子串的中心点作为中心点的回文串的长度，如果回文串的长度等于该子串的长度，则该子串的所有字符的价值之和加入两个项链的价值之和；并对所有的两个项链的价值之和取最大值。

计算方法如下。

首先，设原字符串s，长度为L，在原串的基础上产生辅助串s_new：然后用Manacher算法求出以每个字符为中心的回文串半径序列p[]，并计算原串s中以每个字符为尾的前缀价值和序列sum[]。

然后枚举原字符串中每个可能的切割点i（0≤i≤L-1），得到两个子串s_0…i和s_i+1…L-1：

1）对于左子串s_0…i，在辅助串中的中心点为第i+2个字符，若p[i+2]==i+2，则左子串为回文串，其价值和为sum[i]。

2）对于右子串s_i+1…L-1，在辅助串中的中心点为第i+L+2个字符，若p[i+L+2]==L-i，则右子串为回文串，其价值和为sum[L-1]-sum[i]。

这样，我们就可以计算出切割点为i时的价值和了，然后和当前最优价值Mx比较，调整Mx=max{Mx，切割点为i时的价值和}。显然，枚举完所有可能的分割点后，得出的最优价值Mx便是问题的解。

参考程序（略。本题参考程序的PDF文件和本题的英文原版均可从华章网站下载）