给定一个字符串,例如cabbak,找出其中最长的回文字符串,也就是abba,除了abba这种的,aba也是回文字符串,所谓回文字符串就是指左右两边相同的一种特殊字符串。

    思路分析

    我们先将字符串进行特定格式的填充,将每个字符串之间填充一个#:

    这样的填充是为了可以创造一个唯一的中心点(aba的中心点为b,但是abba不好确定中心点,引入#后,#a#b#b#a很容易确定中心点),并且围绕着这个中心点辐射周边范围为r的区域,在这个区域里左右两边肯定是对称的。我们这里要引入一个概念p,p[i]表示第i个元素的半径(回文字符串是对称的)。

    现在我们要做一个很大胆的猜测,如何利用对称属性快速获取现在的p[i],这里要介绍一些概念:最近的中心点c以及辐射半径r,就是我们每次在找p[i]的时候,我们都要营造出一个已知的回文字符串,这样才能利用对称性快速找到p[i];镜像i',这是在对称性的时候,利用c,可以找到和i对应的i',这样才能利用p[i']快速估算出现在的p[i]。

    完整代码

    1. var preProcess=function(s){
    2.     var n=s.length;
    3.     if(n==0) return '^#';
    4.     var ret='^';
    5.     for(var i=0;i<n;i++){
    6.         ret+='#'+s.charAt(i);
    7.     }
    8.     ret+='#$';
    9.     return ret;
    10. }
    11. var longPalindrome=function(s){
    12.     var T=preProcess(s);
    13.     console.log(T);
    14.     var n=T.length;
    15.     var p=new Array(n);
    16.     var c=0,r=0,max_i=0,max_p=0;
    17.     for(var i=1;i<n-1;i++){
    18.         var i_mirror=2*c-i;
    19.         p[i]=(r>i)?Math.min(r-i,p[i_mirror]):0;
    20.         while(T.charAt(i+1+p[i])==T.charAt(i-1-p[i])){
    21.             p[i]++;
    22.             console.log(i,p[i]);
    23.         }
    24.         if(i+p[i]>r){
    25.             c=i;
    26.             r=i+p[i];
    27.         }
    28.         if(p[i]>max_p){
    29.             max_p=p[i];
    30.             max_i=i;
    31.         }
    32.     }
    33.     console.log(max_i,max_p,T.substring(max_i-max_p,max_i+max_p+1).replace(/#/g,''));
    34. }
    回到顶部
    我要评论

    所有评论

      相关文章