给定一个字符串,例如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]。

完整代码

var preProcess=function(s){
    var n=s.length;
    if(n==0) return '^#';
    var ret='^';
    for(var i=0;i<n;i++){
        ret+='#'+s.charAt(i);
    }
    ret+='#$';
    return ret;
}
var longPalindrome=function(s){
    var T=preProcess(s);
    console.log(T);
    var n=T.length;
    var p=new Array(n);
    var c=0,r=0,max_i=0,max_p=0;
    for(var i=1;i<n-1;i++){
        var i_mirror=2*c-i;
        p[i]=(r>i)?Math.min(r-i,p[i_mirror]):0;
        while(T.charAt(i+1+p[i])==T.charAt(i-1-p[i])){
            p[i]++;
            console.log(i,p[i]);
        }
        if(i+p[i]>r){
            c=i;
            r=i+p[i];
        }
        if(p[i]>max_p){
            max_p=p[i];
            max_i=i;
        }
    }
    
    console.log(max_i,max_p,T.substring(max_i-max_p,max_i+max_p+1).replace(/#/g,''));
}
回到顶部
我要评论

所有评论

返回
邮箱:
绑定
取消
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

邮箱:
绑定邮箱后,若有回复,会邮件通知。
提交
还可以输入500个字