1 public static int Manacher(String A,int n){ 2         char AA[]=A.toCharArray(); 3         char BB[]=new char[2*n+3]; 4         int k=0; 5          for(int i=1;i<=2*n+1;i=i+2){ 6              BB[i]='#'; 7              if(i+1<=2*n+1)BB[i+1]=AA[k++]; 8          } 9          BB[0]='$';//防止数组越界10          BB[2*n+2]='&';//防止数组越界11          int len[]=new int[2*n+3];12          int po=0;//最长回文子串的中心13          int board=0;//最长回文子串的右边界14          int sum=0;//最长回文子串长度15          for(int i=1;i<=2*n+1;i++){16              if(i<=board)len[i]=len[2*po-i]<(board-i)?len[2*po-i]:board-i;17              else len[i]=1;18         while(BB[i+len[i]]==BB[i-len[i]])19             len[i]++;20         if(i+len[i]>board){21             board=i+len[i];22             po=i;23         }24         sum=sum>len[i]?sum:len[i];25     }26          return sum>2?sum-1:0;27 }