最长回文子串问题#
给定一个字符串，找出最长的回文子串，如"waabwswbfd",则最长子串为bwsb.
中心试探法#
最简单的方法，将每一个字符当成中心点，向两边扩展，找到最长的。
时间复杂度为O（n^2）,太慢。
Manacher算法#
这个算法充分利用了字符串匹配问题的特殊性，大大减少了匹配次数，时间复杂度O(n)。
首先算法为了解决字符匹配中的奇偶问题，在每个字符之间插入了一个特别字符‘#’（字符串中不存在就可以）。并且为了数组不越界在首字符处插入了‘$’字符，原因在看完代码后自行思考。
改造后的数组如下：
"$#w#a#a#b#w#s#w#b#f#d#"
算法的关键在于使用了两个变量（也可以用一个变量），id和mx以及一个数组P。id为到i为止以每个字符为中心点的子串能匹配到的最长的一个中心点坐标。P[id]表示到当前为止可以向右的最长距离。mx为P[id] + id即到目前为止可以向右的最远的边界。
根据上面这三个值，有一个重要的结论，即当mx > i时P[i]>=min(P[2id - i], mx - i).
上面这个公式看起来很费解，下面分析一下。
令j = 2id - i；找个例子画一下其实j指的位置是以id为中心点i所对应的位置（就是以id为中心点折叠过去的位置），当mx>i时候说明之前有一个位置以id的中心点的回文子串向右可以越过当前位置i,那么这个子串向左也一定包含对应点j，因为回文是对称的，如果以j为中心点的回文子串被完全包含在以id为中心点的回文子串中，那么以i为中心点的回文子串的长度最少是P[j]的长度。如果没有完全包含，即P[j]>mx-i那么位置在mx以外的字符由于还没匹配到，所以是未知的，只能等匹配到了才能知道是否为回文。
所以可以得到如上的公式。可以看出在这其中mx是必然递增的，即不会回溯。
#include<vector>
#include<iostream>
using namespace std;
const int N=300010;
int n, p[N];
char s[N], str[N];
#define _min(x, y) ((x)<(y)?(x) y))
void kp()
{
int i;
int mx = 0;
int id;
for(i=n; str[i]!=0; i++)
str[i] = 0; //ûÓÐÕâÒ»¾äÓÐÎÊÌâ¡£¡£¾Í¹ý²»ÁËural1297£¬±ÈÈçÊý¾Ý£ºababa aba
for(i=1; i<n; i++)
{
if( mx > i )
p[i] = _min( p[2*id-i], p[id]+id-i );
else
p[i] = 1;
for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
;
if( p[i] + i > mx )
{
mx = p[i] + i;
id = i;
}
}
}
void init()
{
int i, j, k;
str[0] = '$';
str[1] = '#';
for(i=0; i<n; i++)
{
str[i*2+2] = s[i];
str[i*2+3] = '#';
}
n = n*2+2;
s[n] = 0;
}
int main()
{
int i, ans;
while(scanf("%s", s)!=EOF)
{
n = strlen(s);
init();
kp();
ans = 0;
for(i=0; i<n; i++)
if(p[i]>ans)
ans = p[i];
printf("%d\n", ans-1);
}
return 0;
} |
