Manacher 马拉车 算法

介绍

• 作用：找一个字符串中的回文串
• 时间复杂度：o(n)

思路：

需要三个变量：

• len数组，len[i]储存字符串中，以第i个字符为中心的回文串长度
• max储存当前所有找到的回文串中，回文串最右边的字符下标+1
• id为最右边字符下标为max的回文串的中心字符下标

因为已知中心为id的回文串长度为len[id]，所以子串id-len[id]到id+len[id]是关于id对称的

且小于id的回文串长度已经计算出来了，所以当i>id时，以i为中心的回文串长度至少为关于id对称的左边的回文串长度，即len[i]>=len[id-(i-id)]

但是若以id-(i-id)为中心的回文串最左边位置小于以i为中心的回文串的最左边的位置时，不能保证超出部分的字符是相同的，只能保证max-i的部分相同。

综上所述，len[i]>=min(len[id-(i-id)], max-i)

代码：

/**
*初始化字符串
*/
private String init(String s){
	StringBuffer sb = new StringBuffer();
	sb.append("#");
	for(int i=0;i<s.length();++i){
		sb.append(s.charAt(i)).append('#');
	}
	return sb.toString();
}

/**
*马拉车算法
*/
private int[] manacher(String s){
	String str = init(s);
	
	//Manacher
	int[] len = new int[str.length()];
	len[0] = 0;
	int max = 0;	
	int id = 0;

	for(int i=1;i<str.length();++i){
		if(i<max)
			len[i] = Math.min(max-i, len[2*id-i]);//2*id-i ==>id-(i-id)
		else
			len[i] = 1;

		//以i为中心向两边搜索，如果两边相等则回文串长度+1
		while(i+len[i]<str.length() && i-len[i]>=0 &&str.charAt(i+len[i])==str.charAt(i-len[i]))
			len[i]++;

		if(i+len[i]>max){
			max = len[i] + i;
			id = i;
		}
	}
	return len;
}