算法用途

在O(n)的时间判断最长回文子串。

算法思想

由于我们不想当母串字符个数为偶数和母串为奇数时分别写一个程序，所以我们将这个串的字符个数强行变成奇数个。
只要保证在每个字符两边都有一个“#”就可以了。例如：
abcdcbd --> #a#b#c#d#c#b#d#
又为了不判断边界，将新字符串的首项赋为$（或者随意一个用不到的字符），将尾项赋为'0'。
最后新数组为
$#a#b#c#d#c#b#d#0

操作

#define 已知右端点最靠右的回文子串 最右回文子串

设i为当前判断点，id为表示所找到的最右回文子串的中心，mx为最右回文子串的右边界向右一个位置。
我们可以称mx左边为“已知领域”，右侧为“未知领域”。

如果i在最右回文子串内的时候，i的对称点是2*id-i，而当前点i的性质与其对称点的性质一样。
但是我们考虑一个问题，如果是串cbabcdcba???。现在最长串是abcdcba，但是我们先看最后一个点“a”，这个“a”后面的“???”都是还未扫到的值，所以现在“a”的值并不是对称“a”的值，于是我们可以推出：p[i]=min(p[id*2-i],mx-i)，其中p数组记录最右回文子串的长度。
最后需要将i点为中心的回文串补全，因为右边的未知空间没有算入回文串内。

如果i并不在最长回文子串内，则需要继续开拓未知空间，未知空间充满危险，所以需要一点一点开拓。
最后也需要将i点为中心的回文串补全。

算法优势

用已知回文串的性质（即左边的元素（集）等于右边对应的元素（集））更新回文串，降低时间复杂度。

代码

#include <iostream>  
#include <cstring>
#include <algorithm>  
using namespace std;

char s[1000]; //原数组
char s_new[2000]; //插入分隔字符后的新数组
int p[2000]; //Palindrome，记录每个位置的最长回文

int Init(){ //插入分隔字符#
    int len = strlen(s);
    s_new[0] = '$';
    s_new[1] = '#';
    int j = 2;

    for (int i = 0; i < len; i++){
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }

    s_new[j] = '\0';  //字符串结束
    return j;  // 返回 s_new 的长度
}

int Manacher(){
    int len = Init();  //取得新字符串长度并完成向 s_new 的转换
    int max_len = -1;  //最长回文长度

    int id;
    int mx = 0; //mx=i+p[i]即p回文的右边界

    for (int i = 1; i < len; i++){
        if (i < mx)//i在p[id]的回文串之内
            /*
            p[2*id-i]的样例
            cbabcdcba
            id=5，i=8时
            由于对于d左右对称，所以右边的任何一个点都拥有左边对应点的性质。
            但是由于右边有未知领域而
            */
            p[i] = min(p[2 * id - i], mx - i);
        else
            p[i] = 1;//探索未知领域要一步一步探索

        //往两端扩展，判断是否为回文
        while (s_new[i - p[i]] == s_new[i + p[i]])  // 不需边界判断，因为左有'$',右有'\0'
            p[i]++;

        //每走一步i，都要和mx比较，希望mx尽可能的远，这样才能更有机会执行 if(i < mx)这句代码，从而提高效率
        if (mx < i + p[i]){
            id = i;
            mx = i + p[i];
        }

        max_len = max(max_len, p[i] - 1);
    }

    return max_len;
}

int main(){
        scanf("%s", s);
        printf("%d",Manacher());
    return 0;
}

本文链接：http://kaispace.com.cn/index.php/archives/483/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者