本文共 1752 字，大约阅读时间需要 5 分钟。

Manacher算法

一种求回文子串的方法,时间复杂度与空间复杂度为o(N)

import org.junit.Test;public class Math {
       @Test    public void Test()    {
           System.out.println(Manacher("s"));        System.out.println("123".substring(0,2));    }    //马拉车算法的实现时间复杂度o(N),空间复杂度o(N)    //算法步骤:①将数组添加新的字符'#'(其他也可，但是必须是没有在字符串中出现过的)，这样做就不用讨论奇数与偶数    //②遍历数组寻找最长字符子串,在这个过程中用i表示遍历到的索引值,创建一个新的数组p[];    //p[i]表示(针对新数组)从i开始(不包括i)往后面延伸到的最后一个字符的字符个数;还需要center与maxRight    //两个量,maxRight是当前的子串中可以达到的最右边的索引,center是maxRight对应回文子串的    //中心，两者一一对应，    // 那么当i>=maxRight时,这时应该一一的向两端扩散    // 如果i
   
    p[i]=p[mirror]    //②p[mirror]=maxRight-i ---->p[i]=p[mirror]=maxRight-i然后继续扩散    //③p[mirror]>maxRight-i ---->p[i]=maxRight-i    //综上p[i] = min(p[mirror],maxRight-i)    public String Manacher(String s)//    {
           if(s.length()==0)            return  s;        int m,n;        int maxLength=1,index=0;        //初始化应该为center = 0,maxRight = 0        int center=0,maxRight=0;        int mirror;        int []p = new int[s.length()*2+1];        char[] c = Factory(s);        for(int i=1;i
    
     =maxRight)            {
                   p[i] = getPI(c,i);            }            else            {
                   mirror = 2*center-i;                p[i] = java.lang.Math.min(maxRight-i,p[mirror]);            }            //还需要继续扩张            m=i+p[i]+1;            n=i-p[i]-1;            while(m
     
      =0&&c[m]==c[n])            {
                   m++;                n--;            }            if(n<0)                p[i] = i;            else                p[i]= m-i-1;            if(i+p[i]>maxRight)            {
                   maxRight = i+p[i];                center = i;            }            System.out.println(p[i]);            if(maxLength
      
       =0&&n
      
     
    
   

转载地址：http://eslzi.baihongyu.com/