最长回文子串

o(n^2)的解法大家应该都能想到，就是每次以i为中心去两端扩散去找就行了，

下面学习传说中的Manacher解法 o(n)

 

http://blog.163.com/zhaohai_1988/blog/static/2095100852012716105847112/

 

void pk()
{
    int i;
    int mx = 0;
    int id;
    for(i=1; i<n; i++)
    {
        if( mx > i )
            p[i] = MIN( p[2*id-i], mx-i );//找对称点和mx-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;
        }
    }
}

　　

这里只是想说一些自己写过以后自己的理解

原串:waabwswfd

编号              1   2  3 4 5 6  7  8  9 10 11 12 13 14  15 16 17 18 19
新串:             #  w  # a # a #  b  #  w  #   s   #   w  #   f   #   d   #
辅助数组P[]：  1  2   1 2 3 2 1  2  1   2   1   4   1   2   1  2   1   2   1

(发表博客后tmd会显示不对称了，截个图吧)

 

p[i]表示以i为中心的回文串到此回文串的最右边界的距离,如上面的p[12] = 4

这个算法中有两个重要的变量 id 和mx。mx = id + p[id]

mx表示以id为中心的回文串的边界的下一个位置，也就是mx-1是属于id的这个回文串的，mx不属于id,

我对他们的理解有点不一样。  我认为是这样：

首先id不是表示前i个最大的回文串的地方(否则最后输出id不就得了，但是实际算法是还要遍历一次p[]来求最大的p[i])，

而是表示：当前mx能到达的最远的位置。

j是i以id为中心的对称点

id是根据mx来更新的，如果mx大于i(i是当前要更新的结点)，说明以i为中心的回文串有一部分在以id为中心的回文串的里面(由对称关系，id的回文串包含了j的回文串)，但是要考虑j的情况。

比如，当下面是 i=14,此时id=12,j=10,mx =16的情况：

 编号              1   2  3 4 5 6  7  8  9 10 11 12 13 14  15 16 17 18 19
新串:             #  w  # a # a #  b  #  w  #   s  #  w   #   f   #   d   #
辅助数组P[]：  1  2   1 2 3 2 1  2  1   2   1   4   1   2   1   2   1   2   1

                                                    j         id       i        mx

这个时候我们就要想好，用s[i]表示以i为中心的回文串,s[j]是在s[id]中的，s[i]的右边有一部分在i~mx(因为不确定s[i]还会不会增长，这和mx后面的值有关)，所以这里p[i]要取p[j]和mx-i的最小值才能够保证此时的s[i]也是一个回文串。

 

最好的方式还是自己模拟一遍就懂了

 

 

 

#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], mx-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;
}

 

最后是我自己模拟的笔迹