这次要记录的是一个经典的字符串的题目，也是一个经典的马拉车算法的实践。相信在很多地方都会考到或者问到这道题目，这道题目也是字符串类型中必备的基础知识。那么接下来我们看看题目描述：
回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。
Input
输入Str（Str的长度 <= 100000)
Output
输出最长回文子串的长度L。
Input示例
daabaac
Output示例
5
接下来我们直接介绍manacher算法的分析过程，然后再附上代码。
- (1) 解决长度奇偶性带来的对称轴位置问题
Manacher算法首先对字符串做一个预处理，在所有的空隙位置(包括首尾)插入同样的符号，要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的。以插入#号为例：
aba ———> #a#b#a#
abba ———> #a#b#b#a#
插入的是同样的符号，且符号不存在于原串，因此子串的回文性不受影响，原来是回文的串，插完之后还是回文的，原来不是回文的，依然不会是回文。
- (2) 解决重复访问的问题
我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。Manacher定义了一个回文半径数组RL，用RL[i]表示以第i个字符为对称轴的回文串的回文半径。我们一般对字符串从左往右处理，因此这里定义RL[i]为第i个字符为对称轴的回文串的最右一个字符与字符i的距离。对于上面插入分隔符之后的两个串，可以得到RL数组：
char: # a # b # a #
RL : 1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0
i : 0 1 2 3 4 5 6
char: # a # b # b # a #
RL : 1 2 1 2 5 2 1 2 1
RL-1: 0 1 0 1 4 1 0 1 0
i : 0 1 2 3 4 5 6 7 8
上面我们还求了一下RL[i]-1。通过观察可以发现，RL[i]-1的值，正是在原本那个没有插入过分隔符的串中，以位置i为对称轴的最长回文串的长度。那么只要我们求出了RL数组，就能得到最长回文子串的长度。
于是问题变成了，怎样高效地求的RL数组。基本思路是利用回文串的对称性，扩展回文串
我们再引入一个辅助变量MaxRight 表示当前访问到的所有回文子串，所能触及的最右一个字符的位置。另外还要记录下MaxRight
对应的回文串的对称轴所在的位置，记为pos。
它们的位置关系如下。
i在pos位置的示意图
我们从左往右地访问字符串来求RL，假设当前访问到的位置为i即要求RL[i]，在对应上图，i必然是在po右边的(obviously)因为我们已经求了pos，然后从左到右，所有接下来的i是在pos的右边。但我们更关注的是，i是在MaxRight的左边还是右边。我们分情况来讨论。
1）当i在MaxRight的左边
情况1)可以用下图来刻画：
i在pos右边
我们知道，图中两个红色块之间（包括红色块）的串是回文的；并且以i为对称轴的回文串，是与红色块间的回文串有所重叠的。我们找到i关于pos的对称位置j，这个j对应的RL[j]我们是已经算过的。根据回文串的对称性，以i为对称轴的回文串和以j为对称轴的回文串，有一部分是相同的。这里又有两种细分的情况。
1.以j为对称轴的回文串比较短，短到像下图这样。
j回文串很短
这时我们知道RL[i]至少不会小于RL[j]（为什么呢？因为别忘了整体是在pos的回文串中，那么i和j以及它的淡蓝色部分都是关于pos对称相等的），并且已经知道了部分的以i为中心的回文串，于是可以令RL[i]=RL[j]。但是以i为对称轴的回文串可能实际上更长，因此我们试着以i为对称轴，继续往左右两边扩展，直到左右两边字符不同，或者到达边界。
2.以j为对称轴的回文串很长，这么长：
j的回文串很长
这时，我们只能确定，两条蓝线之间的部分（即不超过MaxRight的部分）是回文的，于是从这个长度开始，尝试以i为中心向左右两边扩展，，直到左右两边字符不同，或者到达边界。
不论以上哪种情况，之后都要尝试更新MaxRight和pos，因为有可能得到更大的MaxRight。
2）当i在MaxRight的右边
i在maxright右边
遇到这种情况，说明以i为对称轴的回文串还没有任何一个部分被访问过，于是只能从i的左右两边开始尝试扩展了，当左右两边字符不同，或者到达字符串边界时停止。然后更新MaxRight和pos。
代码实现：
#include <iostream>
#include <string>
using namespace std;
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a>b?b:a;
}
string init(string s)
{
string s1="$#";
int len=s.size();
int i;
for(i=0;i<len;i++)
{
s1+=s[i];
s1+="#";
}
return s1;
}
int Manacher(string s)
{
string s1=init(s);
int mx=0;//最大右边界
int pos;//最大回文串的对称轴
int len=s1.size();
int *p=new int [len];//回文最长半径数组 p[i]=k 代表在位置i的回文串的最长半径为k
int i;
int res=0;
for(i=1;i<len;i++)
{
if(mx>i)//i在mx左边
{
p[i]=min(p[2*pos-i],mx-i);
}
else//i在mx右边 必须一个个匹配
{
p[i]=1;
}
while(s1[i-p[i]]==s1[i+p[i]])//上面得到的是初步的p[i]可能以i为对称轴的回文串更长需要手动检查
{
p[i]++;
}
if(i+p[i]>mx)//更新maxright 最大回文串对称轴位置
{
pos=i;
mx=pos+p[i];
}
res=max(res,p[i]-1);
}
delete [] p;
return res;
}
//manacher算法 时间复杂度O(N)
int main()
{
string s;
cin>>s;
cout<<Manacher(s)<<endl;
return 0;
}
我自己的方法：虽然时间复杂度先对manacher算法会相对高一点，但是至少能AC。
思路：就是遍历字符串的每一个字符，然以当前字符串为中心。向两边去访问看是否符合回文，并记录最长的回文长度。这时就要分情况讨论，有的是奇数型的回文，有的是偶数型的回文串。那么分情况进行计算，然后更新最大值。即可
int main()
{
string s;
cin>>s;
int i;
int len=s.size();
int j;
int cur;
int res=0;
int temp=0;
for(cur=0;cur<len;cur++)
{
i=cur;
j=cur;
if((cur-1>=0&&s[cur]==s[cur-1])||(cur+1<len&&s[cur]==s[cur+1]))
{
while(j<len&&s[j]==s[j+1])
{
j++;
}
while(i>=0&&s[i]==s[i-1])
{
i--;
}
temp=j-i+1;
cur=j;
}
if(i>=0&&j<len&&s[i-1]==s[j+1])
{
while(i>=0&&j<len&&s[i-1]==s[j+1])
{
i--;
j++;
}
if(i==-1&&j==len)
{
temp=len;
}
else
{
temp=j-i+1;
}
cur=j-1;
}
res=max(res,temp);
}
cout<<res<<endl;
return 0;
}
算法讲解参考：
最长回文子串——Manacher 算法
网友评论