求解最长回文子串----Manacher 算法

最长回文子串问题：给定一个字符串，求它的最长回文子串长度。

如果一个字符串正着读和反着读是一样的，那么我们称之为回文串。例如：abba、aaaa、abvcba、123321等

暴力法：遍历字符串的所有子串，对每个字串进行判断。求字符串的所有子串时间复杂度为O(n^{2)，判断回文后，总的时间复杂度为O(n}3)。我们规定在判断回文的时候从最长的子串开始，一旦找到就返回。判断回文的时候，采用从外到内左右成对推进方式进行。

import java.util.Scanner;

public class Main {
    static String str = new String();
    public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		str = in.next();
		System.out.println(sub());
	}
	private static int sub() {
		int low, high;
		for (int len = str.length() - 1; len > 0; len--) {
			for (low = 0, high = low + len; high < str.length(); low++, high++) {
				if (check(low, high)) {
					return high - low + 1;
				}
			}
		}
		return 1;
	}
	private static boolean check(int low, int high) {
		while (low <= high) {
			if (str.charAt(low) == str.charAt(high)) {
				low++;
				high--;
			} else {
				return false;
			}
		}
		return true;
	}
}

从内到外逐个推进方式：由于回文串的特性，我们可以以每个位置为中心进行检查，这样可以不用暴力所有的子串，减少了重复的判断。时间复杂度为O(n^2)。这里要注意检查是要关注奇偶的不同情况，如abba和aba。

import java.util.Scanner;

public class Main2 {
	static String str = new String();
	static int max = 0;
    public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		str = in.next();
		sub();
		System.out.println(max);
	}
	private static void sub() {
		if (str.length() == 1) {
			max = 1;
		}
		for (int i = 0; i < str.length() - 1; i++) {
			check(i, i);
			check(i, i+1);
		}
		
	}
	private static void check(int low, int high) {
		while (low >= 0 && high < str.length()) {
			if (str.charAt(low) == str.charAt(high)) {
				if (high - low + 1 > max) {
					max =  high - low + 1;
				}
				low--;
				high++;
			} else {
				return;
			}
		}
	}
}

Manacher算法：俗称马拉车算法。这是目前求解最长回文串的最优算法。第二种思路在会将从str.charAt(0)一直检查到str.charAt(lstr.length-1)，这样的话还是有许多不必要的操作，而这种算法的核心就在于优化了这一块的判断，跳过某些不必要的值。

由于回文串会出现奇数和偶数不同的情况，如abba和abcba，算法采用插入“#”的方法，使得所有的串都变成奇数串（“$”是占0的位置，从1开始方便操作），这个新的串我们命名为s_new[]。之后定义p[]，用p[i]表示以s_new[i]为中心的最长回文串的半径（包含自身），如abcba的s_new["c"] = 3 (半径为2，再加自身)。我们以字符串abbabcbac为例，最长回文子串为abcba，长度为5。

那么如何计算p[i]就成了这个算法的难点，我们自然不能按着思路二：先令p[i]=1，再以s_new[i]为中心判断两侧是否相等，p[i]++，这是非常低效的。实际上，我们可以不让p[i]初始化为1，我们设定两个变量mx和id，id为s_new[i]的下标（也就是i），mx表示以s_new[id]为中心的最长回文串的右侧边界，以abcba为例，s_new["c"] = 3，id=2（"c"的下标），对应的mx=id+s_new["c"] = 5，刚好就是最右侧"a"的下标。

结合下图，对于i<mx的情况 , 存在p[i] = min(p [2*id-i], mx-i)。

解释一下上面式子，2id-i = j，所以p[2id - i] = p[j]，即以s_new[j]为中心的最长回文串的半径（包含自身）。因为以id为中心的回文子串的长度为mx与其对称点之间的距离，而要求p[i]，则可以利用p[j]来加快查找。

而之所以上面的式子成立是需要深入探讨的，有兴趣的朋友可以参考Manacher算法

import java.util.Scanner;

public class Main {
    static String str = new String();
    static char[] s_new;
    static int[] p;
    public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		str = in.next();
		s_new = new char[str.length() * 2 + 2];
		p = new int[str.length() * 2 + 2];
		
		System.out.println(Manacher());
	}
    
	private static int Manacher() {
		// TODO Auto-generated method stub
		int len = init();
		int maxlen = -1;
		int id = 0;
		int mx = 0;
		for (int i = 1; i < len; i++) {
			if (i < mx) {
				p[i] = Math.min(p[2 * id - i], mx - i);
			} else {
				p[i] = 1;
			}
			while (i + p[i] < s_new.length && i - p[i] >= 0 &&s_new[i - p[i]] == s_new[i + p[i]]) {
				p[i]++;
			}
			if (mx < i + p[i]) {
				id = i;
				mx = i + p[i];
			}
			maxlen = Math.max(maxlen, p[i] - 1);
		}
		return maxlen;
	}

	private static int init() {
		// TODO Auto-generated method stub
		s_new[0] = '$';
		s_new[1] = '#';
		int j = 2;
		
		for (int i = 0; i < str.length(); i++) {
			s_new[j++] = str.charAt(i);
			s_new[j++] = '#';
		}
		return j;
	}
}