算法-字符串之最长回文子串

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

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

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

1. 中心扩展法

中心扩展法可以说是常规算法的改进。首先我们知道，回文串是中心对称的，相比从头到尾遍历字符串的方法，从中间开始向两边扩展，时间会减少一半。
算法思想：把主串中的每一个字符当做回文串的中心，向两边扩展，求出最长的回文子串。其中要注意奇数位的回文子串和偶数位的回文子串的区别。eg:aba的中心是b，而abba的中心应该是bb。使用中心扩展法的时间复杂度是O(n^2)，空间复杂度是O(1)。

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

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

2. 注意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
代码：
代码中有几个需要注意的地方：

1. 在pre函数中，扩展主串时，扩展串的第一个位置是'$'，这是为了诸侯方便处理越界的问题。而字符串越界会出现在哪里呢？就是manacher中的为一个一个while循环那里。
2. 注意重置longest和start时候的值，在介绍str和p的关系的时候已经提到过p[i]-1的意义，在设置longest和start时要考虑到这个关系。（longest是最长回文子串的长度，start是其在原串中的下标）。
3. 理解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<i,说明i不包含在当前计算的回文串中，
             //那么就不能用便捷方法来计算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算法的结果

总结

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