导读

Manacher算法是解决有关回文字符一类的问题。之前寒假看过，琢磨了好久，现在来看，没有那么陌生了，重新理了一遍后，虽然也写了好几遍代码，但感觉已经有是在背代码的感觉了！还是理解万岁。

问题描述

给你一串字符串，返回这个字符串里最长的回文子字符串，或者返回这个最长的回文子字符串的长度。
比如： abccbaaa : 最长回文子字符串为abccba，长度为6
a d s b f p r r p f b l d e : 最长回文子字符串为:bfprrpfb，长度为8
关于什么是回文：
　　 回文就是正着读和反着读的是一样的，或者说他在中间有一个对称轴，关于这个轴两边是镜像的。
　　 顺便贴张图片，前几天在LeetCode上看到的，震惊到我了。

思路

普通解法：
对于字符串中的每个字符，都以他为中心，向两边扩来检查，遇到不相等的就停下，在这个过程中，记录这个最大长度和相对应的字符。
这样对于 奇数个的字符串 还可以用，但对于 偶数个的字符串 就不行了。举个例子：aba，可以找出答案， abba，依次为中心往外扩，得到的答案不对。
所以，这里我们就要对原来的字符串做一些预处理：在每个字符之间插入相同的字符，可以是#，可以是%，甚至可以是原字符串里的字符都可以，这个无所谓，这是起一个辅助作用，帮助我们占位置，是字符都变成 奇数个。

Manacher：
在介绍该算法之前，先介绍需要用到的一些变量：
pArr ： 一个整型数组，长度和经过处理后的字符串的长度相同，每个位置上代表的意思是 在字符串里，以该位置为中心的话，他的最长回文的半径是多长，注意是半径，不是直径。
pR ： 一个整型变量， 意思是目前为值，可以扩到的最长回文半径的右边界，因为这样的话，在pR以左的部分我们都可以利用已知信息来加速这个扩充过程。
center： 一个整型变量， 那个最长回文右边界pR对应着 回文中心，也就是 以center为中心，可以扩到pR长度。

好了，下面开始实施Manacher算法了：
假设我们已经遍历到了i位置，i位置有2中可能
第1中可能： i 在pR的右侧，这样Manacher派不上用场，直接暴力扩就好。
第2中可能： i 在pR的左侧。 这种可能又分为3种小情况。这个过程就是Manacher的核心思想了。
第①： i 关于 center 的对称点 i一撇， i一撇的回文半径我们之前已经算出来了，如果他的回文半径在pR的范围里，那么 i 的回文半径 和 i 一撇的回文半径相同。看着示意图应该就明白了。
（这个示意图我懒得分就贴到一起啦…）

第②; i 关于 center 的对称点 i一撇， i一撇的回文半径我们之前已经算出来了，如果他的回文半径压着pR的范围左边界， 那么i 的回文半径是从pR往右扩的，i-pR的范围可以确定是回文了。 也是看示意图。

第③：i 关于 center 的对称点 i一撇， i一撇的回文半径我们之前已经算出来了，如果他的回文半径已经超过了pR的范围，那个 i 的回文半径长度最长就是到pR了，因为如果比这个长的话，那么原来的pR就不会是现在这个值了，与我们之前定义好的，进而求出来的pR相矛盾。 也是看看示意图。

代码实现

虽然情况是分很多种的，但是写成代码后还是比较简洁的，还是像最前面写的那样，理解就好。

    // 对原字符串 进行 预处理
	public static char[] manacherString(char[] chs) {
   
		char[] chsA = new char[chs.length*2+1];
		int index = 0;
		for(int i = 0; i < chsA.length; i++) {
   
			chsA[i] = i % 2 == 0 ? '#' : chs[index++];
		}
		return chsA; 
	}
	
	// Manacher算法
	public static int manacher(String s) {
   
		if(s == null || s.length() == 0) {
   
			return 0;
		}
		
		char[] charArr = manacherString(s.toCharArray());
		int pR = -1;
		int center = -1;
		int[] pArr = new int[charArr.length];
		int len = Integer.MIN_VALUE;
		
		for(int i = 0; i < charArr.length; i++) {
   
			pArr[i] = i < pR ? Math.min(pR-i, pArr[center*2-i]) : 1;
			while(i+pArr[i] < charArr.length && i-pArr[i] >= 0) {
   
				if(charArr[ i+pArr[i] ] == charArr[ i-pArr[i] ] ) {
   
					pArr[i]++;
				}else {
   
					break;
				} 
			}
			
			if(i + pArr[i] > pR) {
   
				pR = i + pArr[i];
				center = i;
			}
			len = Math.max(len, pArr[i]);
  		}
		
		return len-1; 
	}

小应用

给你一个字符串，要求只能在他的末尾添加字符，使他整体构成一个回文字符串。

思路：

改写Manacher算法，该问题就是求必须包含最后一位字符的最长回文字符串是什么（也就是pR到最后一个位置时就停止了），在吧剩下的字符逆序过来 再 添加到末尾即可。

代码：

	// 对原字符串 进行 预处理
	public static char[] manacherString(char[] chs) {
   
		char[] chsA = new char[chs.length*2+1];
		int index = 0;
		for(int i = 0; i < chsA.length; i++) {
   
			chsA[i] = i % 2 == 0 ? '#' : chs[index++];
		}
		return chsA; 
	}
	
	// 返回的是添加的那部分字符
	public static String manacherAd(String s) {
   
		if(s == null || s.length() == 0) {
   
			return null;
		}
		
		char[] charArr = manacherString(s.toCharArray());
		int center = -1;
		int pR = -1;
		int[] pArr = new int[charArr.length];
		int maxContainsEnd = 0;		// 包含最后一位字符对应的回文是有多长
		
		for(int i = 0; i < pArr.length; i++) {
   
			pArr[i] = i < pR ? Math.min(pR-i, pArr[2*center-i]) : i;
			while(i+pArr[i] < charArr.length && i-pArr[i] >= 0) {
   	// 保证扩的时候不越界
				if(charArr[ i+pArr[i] ] == charArr[ i-pArr[i] ] ) {
   
					pArr[i]++;
				}else {
   
					break;
				}
			}
			
			if(i+pArr[i] > pR) {
   
				pR = i + pArr[i];
				center = i;
			}
			if(pR == charArr.length) {
   
				maxContainsEnd = pArr[i];
				break;
			}
		}
		
		char[] res = new char[ s.length()-maxContainsEnd+1 ];
		for(int i = 0; i < res.length; i++) {
   
			res[res.length-1-i] = charArr[i*2+1];
		}
		
		return String.valueOf(res);
		
	}