找出字符串中对称的子字符串的最大长度（最长回文）

winston

背景：
所谓对称子字符串，就是这个子字符串要么是以其中一个词对称：比如 “aba”， “abcba”；要么就完全对称：比如"abba", "abccba"。
问题：
给你一个字符串，找出该字符串中对称的子字符串的最大长度。
思路：
首先，我们用字符数组 char[] array 来保持这个字符串，假设现在已经遍历到第 i 个字符，要找出以该字符为“中心”的最长对称字符串，我们需要用另两个指针分别向前和向后移动，直到指针到达字符串两端或者两个指针所指的字符不相等。因为对称子字符串有两种情况，所以需要写出两种情况下的代码：
1. 第 i 个字符是该对称字符串的真正的中心，也就是说该对称字符串以第 i 个字符对称， 比如： “aba”。代码里用 index 来代表 i.

2.         public static int maxLengthMiddle(char[] array, int index) {
3.                 int length = 1; //最长的子字符串长度
4.                 int j = 1; //前后移动的指针
5.                 while ((array[index - j] == array[index + j]) && (index - j) >= 0 && array.length > (index + j)) {
6.                         length += 2;
7.                         j++;
8.                 }
9.                
10.                 return length;
11.         }

复制代码

2. 第 i 个字符串是对称字符串的其中一个中心。比如“abba”。

2.         public static int maxLengthMirror(char[] array, int index) {
3.                 int length = 0; //最长的子字符串长度
4.                 int j = 0; //前后移动的指针
5.                 while ((array[index - j] == array[index + j + 1]) && (index - j) >= 0 && array.length > (index + j + 1)){
6.                         length += 2;
7.                         j++;
8.                 }
9.                
10.                 return length;
11.         }

复制代码

有了这样两个函数，我们只需要遍历字符串里所有的字符，就可以找出最大长度的对称子字符串了。

2.         public static int palindrain(char[] array) {
3.                 if (array.length == 0) return 0;
4.                 int maxLength = 0;
5.                 for (int i = 0; i < array.length; i++) {
6.                         int tempMaxLength = - 1;
7.                         int length1 = maxLengthMiddle(array, i);
8.                         int length2 = maxLengthMirror(array, i);
9.                         tempMaxLength = (length1 > length2) ? length1 : length2;
10.                         if (tempMaxLength > maxLength) {
11.                                 maxLength = tempMaxLength;
12.                         }
13.                 }
14.                 return maxLength;
15.         }

复制代码

因为找出以第 i 个字符为“中心”对称字符串复杂度为 O（N），所以整个算法的复杂度为O（N^2）。

另一种方法是把原始字符串反转，这样最长对称子字符串问题可以转化成求两个字符串的最长公共子字符串问题（备注：不是最长公共子序列）。
有一种可以把复杂度降到O（N）的算法，但是这个算法要利用 suffix tree， 有兴趣的可以搜索一下。

作者：beiyeqingteng 发表于2011-12-23 4:31:40 原文链接