[hiho 01]最长回文子串、Manacher算法

 

- 基础方法:枚举子串,判断是否为回文串。

- 改进:枚举中间位置,向两侧拓展。

- 再改进:利用以前的信息,使得不用每个新位置都从长度1开始拓展。

- 优化:将字符串预处理为奇数长度以避免考虑条件分支。

- 再优化:开头加入特殊字符避免考虑边界。

 

Manacher 算法:

id 是中心点,mx 是其边界。P[i] 表示以 i 为中心的最长回文子串的折半长度。

只要 i < mx, 以 i 为中心的回文子串就可以不必从长度1开始找,而从min{P[j], mx - i}开始(其中j为i关于id的对称点)。

当mx可以向右前进时(i + P[i] > mx),改变id和mx的值。

技术分享

技术分享

具体实现的代码如下:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_SIZE 1000000
char str[2 * MAX_SIZE + 10];
int p[2 * MAX_SIZE + 10];

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", str);
        int n = strlen(str);
        for (int i = n - 1; i >= 0; i--) {
            str[2*i+2] = str[i];
            str[2*i+3] = ‘#‘;
        }
        str[0] = ‘$‘;
        str[1] = ‘#‘;
        memset(p, 0, sizeof(p));
        int id = 0, mx = 0;
        int res = 0;
        for (int i = 1; i < 2*n+4; i++) {
            p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
            while (str[i + p[i]] == str[i - p[i]]) {
                p[i]++;
            }
            res = max(res, p[i]);
            if (i + p[i] > mx)
            {
                mx = i + p[i];
                id = i;
            }
        }
        printf("%d\n", res - 1);
    }
    return 0;
}

 

吐槽:p数组大小没乘2,但是hiho居然报wa。白找了半天错。

 

Ref:http://taop.marchtea.com/01.05.html

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。