寻找最长回文串长度的一个动态规划解法

今天某面试题，要在任意给定的字符串中，寻找最长回文串的长度。

注：回文串是指abc、abbc、aaabccc、aaaccc这种左右对称的字符串。

比如：abcaabbbaad字符串中，最长回文串的长度是7。

 

/**
 * 思路：<br>
 * 动态规划。一个指针从头往后遍历；一个指针从后往前遍历，把之前比较过的结果存到二维数组内，每个单元表示截止匹配到某一个字符串，所属的最长子串长度。<br>
 * 因为从前往后和从后往前遍历是同一个串，所以这个二维数组是轴对称的。<br>
 * 关键是这一步：当某时刻匹配上时，statArr[i][j] = statArr[j][i] = statArr[i - 1][j + 1] + 1，后一次的结果为前一次的结果加一。
 * 
 * @author Ray Chase
 * 
 */
public final class SymmetricalSearch {

	/**
	 * default constructor
	 */
	private SymmetricalSearch() {
	}

	/**
	 * 寻找最长的对称字符串长度
	 * 
	 * @param word
	 *            被查字串
	 * @return 最长的字符串片段长度
	 */
	public static int getLongestSymmetricalSection(char[] word) {

		// guard condition
		if (null == word || 0 == word.length)
			return 0;

		// 存放状态的数组，取值表示最近一次匹配的字串长度
		int[][] statArr = new int[word.length][word.length];

		// 最长的字串的长度
		int max = 0;

		// 最近一行是否匹配上
		boolean matched;

		// i表示word自左向右方向遍历的指针，在动态规划的map中表示行号
		for (int i = 0; i < word.length; i++) {

			// 最近一行是否匹配上，每行开头预置位false
			matched = false;

			// j表示word自右向左方向遍历的指针，在动态规划的map中表示列号
			for (int j = word.length - 1; j >= 0; j--) {

				// 如果在边界，匹配上了
				if (0 == i || word.length - 1 == j) {
					if (word[i] == word[j]) {
						matched = true;
						statArr[i][j] = statArr[j][i] = 1;
					}
				}
				// 不在边界且匹配上了，最近一次匹配的长度为上次匹配的长度+1
				else if (word[i] == word[j]) {
					matched = true;
					statArr[i][j] = statArr[j][i] = statArr[i - 1][j + 1] + 1;
					// 更新最长字串长度和字串起始位置
					if (statArr[i][j] > max) {
						max = statArr[i][j];
					}
				}
			}

			// 如果本行没有匹配上且当前发现的最大匹配长度已经大于等于剩下可能匹配的最大长度，没有必要继续了
			if (!matched && max >= word.length - (i + 1)) {
				break;
			}
		}

		//不存在长度为1的对称字串
		return 1 == max ? 0 : max;
	}
}

 

 

这个算法其实还有改进的空间，譬如，动态规划不需要N平方的空间，因为每次使用这个statArr的时候，只用一行的数据，因此空间复杂度可以由n平方变为n。

具体的办法，还有其他改进的办法，欢迎大家讨论。:)

 

附，测试用例：

public class SynmetricalSearchTest extends TestCase {

	public void testAbnormal() {
		assertEquals(0, SymmetricalSearch.getLongestSymmetricalSection(null));
		assertEquals(0, SymmetricalSearch.getLongestSymmetricalSection(""
				.toCharArray()));
	}

	public void testOdd() {
		assertEquals(5, SymmetricalSearch.getLongestSymmetricalSection("12321"
				.toCharArray()));
		assertEquals(3, SymmetricalSearch.getLongestSymmetricalSection("121"
				.toCharArray()));
	}

	public void testEven() {
		assertEquals(4, SymmetricalSearch.getLongestSymmetricalSection("1221"
				.toCharArray()));
		assertEquals(6, SymmetricalSearch.getLongestSymmetricalSection("123321"
				.toCharArray()));
	}

	public void testMixOdd() {
		assertEquals(5, SymmetricalSearch
				.getLongestSymmetricalSection("asf12321drf".toCharArray()));
		assertEquals(3, SymmetricalSearch.getLongestSymmetricalSection("121"
				.toCharArray()));
	}

	public void testMixEven() {
		assertEquals(4, SymmetricalSearch
				.getLongestSymmetricalSection("6781221787".toCharArray()));
		assertEquals(6, SymmetricalSearch
				.getLongestSymmetricalSection("55512332144".toCharArray()));
	}

	public void testMixNone() {
		assertEquals(0, SymmetricalSearch.getLongestSymmetricalSection("6784"
				.toCharArray()));
	}

	public void testNesting() {
		assertEquals(7, SymmetricalSearch
				.getLongestSymmetricalSection("3332333".toCharArray()));
		assertEquals(6, SymmetricalSearch
				.getLongestSymmetricalSection("af323323ed".toCharArray()));
	}

}

 

---------------------------------------------------------------------------------------------------------------------------------

2012-3-26 更新：

同事提点我，这个做法是有问题的，如果出现这样的字符串，比如：abcdba，这个做法会认为ab是最大子串，那就错了，因此，这个算法在每次发现疑似最大回文串时都要进行校验，当然，这样效率就低了不少。

网上比较多的相对比较简单的正确解法是后缀树解法，这里有一位高人的blog。

不过，小罗同学说，甚至可以把复杂度降到O(n)！太不可思议了是不是？据说这叫Manacher算法，看这里和这里。

 

文章系本人原创，转载请注明出处和作者