扩展kmp求最长回文子串_算法-字符串之最长回文子串

上一篇KMP算法之后好几天都没有更新，今天介绍最长回文子串。

首先介绍一下什么叫回文串，就是正着读和倒着读的字符顺序都是一样的，eg:level，noon。而回文子串，顾名思义，就是主串中满足回文性质的子串。

求解的常规思想，就是先求出主串的所有子串，在判断是否是回文串，然后选出最长的，这一种方法的时候复杂度较高，是O(n^3)，所以一般不采用这种方法，下面介绍两种方法求解。

1. 中心扩展法

中心扩展法可以说是常规算法的改进。首先我们知道，回文串是中心对称的，相比从头到尾遍历字符串的方法，从中间开始向两边扩展，时间会减少一半。

算法思想：把主串中的每一个字符当做回文串的中心，向两边扩展，求出最长的回文子串。其中要注意奇数位的回文子串和偶数位的回文子串的区别。eg:aba的中心是b，而abba的中心应该是bb。使用中心扩展法的时间复杂度是O(n^2)，空间复杂度是O(1)。

代码

核心算法是l2r的部分，以传入的mid为回文串的中心计算最长的回文子串，其中需要注意的地方有两点：

l2r中的第一个while循环，之前提到过要注意奇数位的回文串和偶数位的回文串，在代码中，判断中心点的字符和右边的字符是否相等，就可以跳过偶数位的中心点。

注意l2r中返回语句，从第二个while循环中跳出的时候，已经多进行了一步left–，right++的操作了。

int longest;//子串长

int start;//最长回文子串在主串中的起始位置

/*计算以mid为中心的最长回文子串*/

int l2r(char *string, int mid) {

int len = strlen(string);

int left = mid – 1, right = mid + 1;

//跳过相同的部分

while (string[right] == string[mid])

right++;

while (left > 0 && right < len){

if (string[left] == string[right]) {

//从中间开始算，各向外移一位

start = left;

left–;

right++;

}

else {

break;

}

}

//重置回文串的起始位置

if (left < 0)

start = 0;

//printf(“\tstart:%d left:%d right:%d len:%d\n”, start, left, right, right – 1 – (left + 1) + 1);

//跳出while循环的时候，要么是index不满足条件，要么是当前right和left的位置字符不等，都要在将right,left还原成删一个状态才能计算回文串长

return right – 1 – (left + 1) + 1;

}

/*计算最长回文子串的长度*/

int longestPald(char *string) {

int len = strlen(string);

if (string == NULL || len == 0)

assert(“ERROR”);

if (len == 1){

longest = 1;

start = 0;

return 1;

}

for (int i = 0; i < len; i++){//遍历整个主串，以它的每一位为回文串的中心，计算最长的回文串

int tempLen = l2r(string, i);

if (tempLen > longest) {

longest = tempLen;

}

}

return 0;

}

int main(void)

{

char string[] = “abcdeedcbdac”;

longestPald(string);

printf(“\t%s的最长回文子串:\n”, string);

printf(“\t起始位置：%d 串长：%d\n”, start, longest);

system(“pause”);

return 0;

}

结果：

abcdeedcbdac的最长回文子串：bcdeedcb

2. 动态规划法？？？

之前看到网上有很多用动态规划法求解最长回文子串的，但是我看了之后觉得有问题。动态规划法中是用二维矩阵保存回文串长，c[i][j]表示主串中s[i…j]是回文串，当前位置的c[i][j]需要依赖于c[i+1][j-1]，但是有的地方c[i+1][j-1]是不知道的，反而觉得用递归来计算矩阵c会更好。不知道是我理解错误还是这个方法确实不对。如果有用动态规划法求解出最长回文子串的，还请赐教~

3. Manacher算法

这是几个方法中最为高效的方法，时间复杂度为O(n).Manacher算法也是利用回文串的对称性，标记回文串的中间位，向两边遍历。同样是标记中间位，向两边遍历，那它和中心扩展法有什么区别呢？

区别：中心扩展法的思想是以主串的每一个字符为中心，计算最长的回文子串，外层循环执行n次，内存循环至多2/n次；而Manacher的中心字符并不是这样的，Manacher利用之前计算过的回文子串，巧妙的计算出新的中心点。但同时它也做出了一些折中的处理，比如说，要确定唯一的中心点，所以要扩展主串。

算法思想：Manacher采用从中间向两边遍历得到最长回文子串的思想，将原来的主串进行扩展，这个算法严格要求对称，只允许有一个中心点。eg:abc– > #a#b#c#，这样不管回文串是奇数位还是偶数位都都会变成奇数位的，满足只有一个中心字符的要求。Manacher利用之前计算的回文子串，避免了一些重复的回文子串的计算。

辅助变量：

既然要利用之前求得信息，就需要记录。

p[]:数组p保存的是主串中以某个字符为中心的最长回文子串的半径，eg：p[i]存储的是以str[i]为中心的最长回文串的半径，这个半径值是在扩展之后的字符串中。

mid:保存得到的回文串的中心点。

max:保存当前的回文串的影响范围，也就是这个回文串的右边界。

注：mid和max的值是由最长回文串计算得到的。

现在，我们来看一下str和p的关系，便于理解。s是在原来的字符串

s和p的关系

接下来计算p[],这时要用到max和mid。先解释一下最难懂的地方。利用之前计算的回文子串的信息计算当前的p[i]，现则最小的值。

p[i] = (max – i) > p[j] ? p[j] : (max-i);

解释：(以下解释摘自另一篇博客)

1.当 mx – i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。

当 mx – i > P[j] 的时候

2.当 P[j] > mx – i 的时候，以S[j]为中心的回文子串不完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx – i。至于mx之后的部分是否对称，就只能一个一个匹配了。

P[j] > mx – i 的时候

接下来解释算法为线性的原因：(算法中其实有两层循环)

image.png

代码：

代码中有几个需要注意的地方：

在pre函数中，扩展主串时，扩展串的第一个位置是’$’，这是为了诸侯方便处理越界的问题。而字符串越界会出现在哪里呢？就是manacher中的为一个一个while循环那里。

注意重置longest和start时候的值，在介绍str和p的关系的时候已经提到过p[i]-1的意义，在设置longest和start时要考虑到这个关系。(longest是最长回文子串的长度，start是其在原串中的下标)。

理解p[i] = (max – i) > p[j] ? p[j] : (max-i);很重要，结合代码中的注释和上面的图多理解。

int pre(char *string, char *strCopy) {

strCopy[0] = ‘$’;

int j = 1;

for (int i = 0; i < strlen(string); i++) {

strCopy[j++] = ‘#’;

strCopy[j++] = string[i];

}

strCopy[j] = ‘#’;

return j + 1;//表示strCopy的长度

}

void manacher(char *str,int n) {

int p[MAXLEN];//数组p中保存字符串str中以某一点为中心点的最长回文子串的半径

p[0] = 0;//p[0]对应str[0]–>$

//max存储之前计算的回文子串的右边界，mid保存当前的回文子串的中心,这两个值都不一定是最长回文子串求得

int max = 0, mid = 1;

for (int i = 1; i < n; i++) {

if (max > i)

{

int j = 2 * mid – i;//j是字符串中i关于mid的对称点

p[i] = (max – i) > p[j] ? p[j] : (max – i);//!!!

}

else {//否则max

//那么就不能用便捷方法来计算p[i]，只能一个一个计算

p[i] = 1;//初始值为1

}

//基于当前以i为中心的回文串的半径，计算下一个位置的字符是否满足回文。这里会出现越界的问题！！！

while (str[i – p[i]] == str[i + p[i]]){

p[i]++;

}

if ((i + p[i]) > max){

max = i + p[i];//当前计算得到的回文串已经大于之前计算的边界了，重置边界

mid = i;

}

if (longest < p[i] – 1){//p[i]-1就是原串中以i为中心的回文串的长度

longest = p[i] – 1;

//在遇到最长回文子串包含第0个字符的时候，start计算得-1，所以这里要处理一下

if ((i – p[i] – 1) < 0)

start = 0;

else

start = i – p[i] – 1;

}

}

}

int main(void)

{

char string[] = “acab”;//”abcdeedcbdac”;

char strCopy[MAXLEN];

int len = pre(string, strCopy);

printf(“原串：%s –>”, string);

//输出strCopy

for (int i = 0; i < len; i++){

printf(“%c”, strCopy[i]);

}

printf(“\n”);

manacher(strCopy,len);

printf(“\t%s的最长回文子串:\n”, string);

printf(“\t起始位置：%d 串长：%d\n”, start, longest);

system(“pause”);

return 0;

}

结果：

manacher算法的结果

总结

好了，这次就到这里了。不足之处，欢迎指正。