字符串中最长的回文字符串长度

大家好，又见面了，我是你们的朋友全栈君。

1、回文字符串

回文字符串是指aba类型的字符串，即字符串关于中间字符对称。判断字符串中是否含有回文、得到最长回文字符串的长度、得到不同回文字符串的个数等等，是经常考察的编程题目。

2、之前采用的一种比较笨的得到最长回文字符串的方法

思想：双重指针遍历，根据回文字符串的特点，回文开始的字符与结尾处字符相同……那么一个指针i从前向后遍历，一个指针j从后向前遍历，如果出现相同的字符，此时计数值加2，i后移一位（保留i的位置，下次外层循环），j前移一位；如果不相等，j指针前移；（注意，此时考虑奇数回文情况，即回文的最中间字符只出现一次，那么需要增加判断，此时计数加1）。记录本次循环的最大回文长度，每次循环跟新该最大值，直到循环结束。。。。代码如下：

public static int return_long(String s){    
		char str[]=new char[s.length()];
		str=s.toCharArray();
		int count=0,max=0;
		for(int i=0;i<s.length();i++){
			int k=i;
			for(int j=s.length()-1;j>k;j--){
				if(str[k]==str[j]){
					count+=2;
					k++;										
				}
				 if(j==(k+1))count++;
			}			
			if(max<count){max=count;}
			count=0;
		}
		if(max>=s.length()||s.length()<=1)return 0;
		return max;
	}

3、manacher方法

2中所述方法没有更好的利用回文字符串的特性，时间复杂度为O(N*N)，网上普遍使用一种更为快捷的manacher方法，其时间复杂度仅有O(N)。原文请看这里.

该方法的主要思想是利用回文字符串的对称特性，加速查找过程。假设rad[i]表示字符串s的位置i处的最长回文半径，那么s[i-rad[i],i-1]=s[i+1,i+rad[i]]。

很明显,求出了所有的rad,就求出了所有的长度为奇数的回文子串. 至于偶数的怎么求,最后再讲. 假设现在求出了rad[1..i-1],现在要求后面的rad值,并且通过前面的操作,得知了当前字符i的rad值至少为j.现在通过试图扩大j来扫描,求出了rad[i].再假设现在有个指针k,从1循环到rad[i],试图通过某些手段来求出[i+1,i+rad[i]]的rad值. 根据定义,黑色的部分是一个回文子串,两段红色的区间全等. 因为之前已经求出了rad[i-k],所以直接用它.有3种情况:

字符串中最长的回文字符串长度

①rad[i]-k<rad[i-k] 如图,rad[i-k]的范围为青色.因为黑色的部分是回文的,且青色的部分超过了黑色的部分,所以rad[i+k]肯定至少为rad[i]-k,即橙色的部分.那橙色以外的部分就不是了吗?这是肯定的.因为如果橙色以外的部分也是回文的,那么根据青色和红色部分的关系,可以证明黑色部分再往外延伸一点也是一个回文子串,这肯定不可能,因此rad[i+k]=rad[i]-k.为了方便下文,这里的rad[i+k]=rad[i]-k=min(rad[i]-k,rad[i-k]).

字符串中最长的回文字符串长度

②rad[i]-k>rad[i-k] 如图,rad[i-k]的范围为青色.因为黑色的部分是回文的,且青色的部分在黑色的部分里面,根据定义,很容易得出:rad[i+k]=rad[i-k].为了方便下文,这里的rad[i+k]=rad[i-k]=min(rad[i]-k,rad[i-k]).

根据上面两种情况,可以得出结论:当rad[i]-k!=rad[i-k]的时候,rad[i+k]=min(rad[i]-k,rad[i-k]). 注意:当rad[i]-k==rad[i-k]的时候,就不同了,这是第三种情况:

字符串中最长的回文字符串长度

如图,通过和第一种情况对比之后会发现,因为青色的部分没有超出黑色的部分,所以即使橙色的部分全等,也无法像第一种情况一样引出矛盾,因此橙色的部分是有可能全等的,但是,根据已知的信息,我们不知道橙色的部分是多长,因此就把i指针移到i+k的位置,j=rad[i-k](因为它的rad值至少为rad[i-k]),等下次循环的时候再做了. 整个算法就这样. 至于时间复杂度为什么是O(n),我已经证明了,但很难说清楚.所以自己体会吧. 上文还留有一个问题,就是这样只能算出奇数长度的回文子串,偶数的就不行.怎么办呢?有一种直接但比较笨的方法,就是做两遍(因为两个程序是差不多的,只是rad值的意义和一些下标变了而已).但是写两个差不多的程序是很痛苦的,而且容易错.所以一种比较好的方法就是在原来的串中每两个字符之间加入一个特殊字符,再做.如:aabbaca,把它变成(#a#a#b#b#a#c#a#)，左右的括号是为了使得算法不至于越界。这样的话,无论原来的回文子串长度是偶数还是奇数,现在都变成奇数了.

代码如下：

import java.util.NoSuchElementException;
import java.util.Scanner;

/*
 * 字符串中最大回文字符串的长度，manacher算法，时间复杂度为O(n).
 * 参照：http://www.cnblogs.com/Lyush/p/3221503.html
 * manacher算法计算任意以某个字符为中心的最长回文串长度。通过填充字符串，使得该算法可以适应奇数与偶数情况。
 */
public class Manacher {
	public static void manacher(char s[],int length,int rad[]){
		for(int i=1,j=0,k;i<length;i+=k){
			while (s[i-j-1] == s[i+j+1]) ++j;
	        rad[i] = j;
	        for (k = 1; k <= rad[i] && rad[i-k] != rad[i]-k; ++k) { // 利用类似镜像的方法缩短了时间 
	            rad[i+k] = Math.min(rad[i-k], rad[i]-k);
	        }
	        j = Math.max(j-k, 0);
		}
	}
	public static void main(String[]args){
		Scanner sc=new Scanner(System.in);
		try{
			String s=sc.next();
			int len=2*s.length()+3;
			char cpy[]=new char[len+10];//使用足够的空间（why?）
			cpy[0]='(';cpy[1]='#';//填充字符串，使得字符串中字符个数为奇数，所得半径即为最长回文长度
			for(int i=0,j=2;i<s.length();++i,j+=2){
				cpy[j]=s.charAt(i);
				cpy[j+1]='#';
			}
			cpy[len-1]=')';
			int seq[]=new int[len+10];
			manacher(cpy,len,seq);
			int Max = 1;
	        for (int i = 0; i < len; ++i) {
	            Max = Math.max(Max, seq[i]);
	        }
	        System.out.println(Max);

		}catch(NoSuchElementException e){
			e.getStackTrace();
		}
	}
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/135590.html原文链接：https://javaforall.cn