Skip to the content.

1 Manacher算法

1.1 简介

回文串概念:一个字符串是轴对称的,轴的左侧和右侧是逆序的关系,例如”abcba”,”abccba”

Manacher算法解决在一个字符串中最长回文子串的大小,例如”abc12321ef”最长回文子串为”12321”大小为5

回文串的用途,例如我们可以把DNA当成一个字符串,有一些基因片段是回文属性的,在生理学上有实际意义

1.2 字符串最长回文子串暴力解

遍历str,以i为回文对称的回文串有多长,在i位置左右扩展。所以字符串”abc123df”

i为0的时候,回文串为”a”,长度为1;

i为1的时候,回文串为”b”,左边和右边不相等,长度为1;

i为1的时候,回文串为”b”,长度为1;

。。。。。。

此种方式,无法找到以一个虚轴的最长回文串

所以我们可以通过填充字符,来解决,例如”31211214”我们前后和字符间填充’#’得到”#3#1#2#1#1#2#1#4#”,利用该串进行上述步骤来寻找。

i为0的时候,回文串为”#”,长度为1;

i为1的时候,回文串为”#3#”,长度为3;

i为8的时候,回文串为”#1#2#1#1#2#1#”,长度为13;

可以找到所有基数或者偶数的所有回文串,但是回文串的长度和原始回文串长度的关系为:当前回文串长度除以2,得到原始串中各个位置的回文串长度

复杂度最差情况是,所有字符长度为n,且所有字符都相等。经过我们的填充,字符串规模扩展到2n+1。每次寻找,都会寻找到左边界或者右边界,该方法的事件复杂度为O(N*N)

Manacher算法解决该类问题,O(N)复杂度!

1.3 Manacher解决最长回文串O(N)

概念1:回文半径和回文直径,回文直径指的是,在我们填充串中,每个位置找到的回文串的整体长度,回文半径指的是在填充串中回文串从i位置到左右边界的一侧的长度

概念2:回文半径数组,对于填充串每个i位置,求出来的回文串的长度,都记录下来。pArr[]长度和填充串长度相同

概念3:回文最右右边界R和中心C,R和C初始为-1。例如扩展串为”#1#2#2#1#3#”。O(N)

Manacher算法的核心概念就是,回文半径数组pArr[],回文最右边界R,中心C

在遍历填充数组时,会出现i在R外,和i在R内两种情况。

当i在R外时,没有任何优化,继续遍历去寻找。当i在R内涉及到Manacher算法的优化。i在R内的时候,i肯定大于C,我们可以根据R和C求出左边界L,也可以根据i和C求出以C堆成的i’。

经过以上的情况,整体O(N)复杂度

Code:

public class Code01_Manacher {

	public static int manacher(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		// "12132" -> "#1#2#1#3#2#"
		char[] str = manacherString(s);
		// 回文半径的大小
		int[] pArr = new int[str.length];
		int C = -1;
		// 算法流程中,R代表最右的扩成功的位置。coding:最右的扩成功位置的,再下一个位置,即失败的位置
		int R = -1;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < str.length; i++) {
			// R是第一个违规的位置,i>= R就表示i在R外
			// i位置扩出来的答案,i位置扩的区域,至少是多大。
                        // 2 * C - i 就是i的对称点。
                        // 得到各种情况下无需验的区域
			pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
      
                        // 右侧不越界,且左侧不越界,检查需不需要扩
			while (i + pArr[i] < str.length && i - pArr[i] > -1) {
				if (str[i + pArr[i]] == str[i - pArr[i]])
					pArr[i]++;
				else {
					break;
				}
			}
                        //i的右边界有没有刷新之前的最右边界。R刷新C要跟着刷新
			if (i + pArr[i] > R) {
				R = i + pArr[i];
				C = i;
			}
			max = Math.max(max, pArr[i]);
		}
		return max - 1;
	}

	public static char[] manacherString(String str) {
		char[] charArr = str.toCharArray();
		char[] res = new char[str.length() * 2 + 1];
		int index = 0;
		for (int i = 0; i != res.length; i++) {
			res[i] = (i & 1) == 0 ? '#' : charArr[index++];
		}
		return res;
	}

	// for test
	public static int right(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		char[] str = manacherString(s);
		int max = 0;
		for (int i = 0; i < str.length; i++) {
			int L = i - 1;
			int R = i + 1;
			while (L >= 0 && R < str.length && str[L] == str[R]) {
				L--;
				R++;
			}
			max = Math.max(max, R - L - 1);
		}
		return max / 2;
	}

	// for test
	public static String getRandomString(int possibilities, int size) {
		char[] ans = new char[(int) (Math.random() * size) + 1];
		for (int i = 0; i < ans.length; i++) {
			ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
		}
		return String.valueOf(ans);
	}

	public static void main(String[] args) {
		int possibilities = 5;
		int strSize = 20;
		int testTimes = 5000000;
		System.out.println("test begin");
		for (int i = 0; i < testTimes; i++) {
			String str = getRandomString(possibilities, strSize);
			if (manacher(str) != right(str)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("test finish");
	}

}

1.4 例题

给定一个字符串str,只可在str后添加字符,把该串变成回文字符串最少需要多少个字符?

解题思路:转化为必须包含最后一个字符的最长回文串多长?例如,”abc12321”,以最后一个1的最长回文串为”12321”,那么最少需要添加”cba”3个字符

public class Code02_AddShortestEnd {

	public static String shortestEnd(String s) {
		if (s == null || s.length() == 0) {
			return null;
		}
		char[] str = manacherString(s);
		int[] pArr = new int[str.length];
		int C = -1;
		int R = -1;
		int maxContainsEnd = -1;
		for (int i = 0; i != str.length; i++) {
			pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
			while (i + pArr[i] < str.length && i - pArr[i] > -1) {
				if (str[i + pArr[i]] == str[i - pArr[i]])
					pArr[i]++;
				else {
					break;
				}
			}
			if (i + pArr[i] > R) {
				R = i + pArr[i];
				C = i;
			}
			if (R == str.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] = str[i * 2 + 1];
		}
		return String.valueOf(res);
	}

	public static char[] manacherString(String str) {
		char[] charArr = str.toCharArray();
		char[] res = new char[str.length() * 2 + 1];
		int index = 0;
		for (int i = 0; i != res.length; i++) {
			res[i] = (i & 1) == 0 ? '#' : charArr[index++];
		}
		return res;
	}

	public static void main(String[] args) {
		String str1 = "abcd123321";
		System.out.println(shortestEnd(str1));
	}

}