最短回文代码,Java代码库,德仔网

代码语言

代码分类

【Java】最短回文

作者:会飞的章鱼 / 发布于2015/6/2/ 504


	public static String shortestPalindrome(String s) {
	 int len = s.length();
	 if(len == 1){
	 return s;
	 }
	 StringBuffer sb = new StringBuffer();
	 sb.append("#");
	 for(int i=0;i<len;i++){
	 sb.append(s.charAt(i)).append("#");
	 }
	 int mx =0;
	 int id =0;
	 int[] P= new int[2*len+1];
	 P[0]=0;
	
	 for(int i=1;i<2*len+1;i++){
	 if(mx>i){
	 P[i]=Math.min(P[2*id-i], mx-i);
	 }else{
	 P[i]=0;
	 }
	 while((i-P[i]-1)>=0&& (i+P[i]+1)<(2*len+1)&&sb.charAt(i-P[i]-1) == sb.charAt(i+P[i]+1)){
	 P[i]++;
	 }
	 if(i+P[i]>mx){
	 mx =i+P[i];
	 id = i;
	 }
	
	 }
	
	 int plen =1;
	 for(int i=(2*len+1)/2; i>-1;--i){
	 if(P[i] == i){
	 plen =i;
	 break;
	 }
	 }
	
	 StringBuffer sb1 =new StringBuffer( s.substring(plen));
	 sb1.reverse();
	 return sb1.append(s).toString();
	 }

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　回文　

同语言下

可能有用的

会飞的章鱼贡献的其它代码(11)