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

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

 

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

 

void pk(){    int i;    int mx = 0;    int id;    for(i=1; i
     
       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
     
      #include
      
       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
       
         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
        
         ans)    ans = p[i];  printf("%d\n", ans-1); } return 0;}
        
       
      
     

 

最后是我自己模拟的笔迹