Manacher

FJ_00460 · 2025-03-02 20:55:59 · 个人记录

manacher

相关定义：回文字符串

问题：求最长回文子串

1.暴力

找出所有子串，遍历每个子串判断它们是否为回文串

复杂度： O(n^2)

2.manacher

p[i]：第i个节点的回文半径 方法：加入没有的字符，如 # 等。 用p[i]表示第i个节点回文的半径。

最大的 p[i] - 1就是答案。

从数值上看，插入玩字符后，回文串长度为原串长度 2 + 1.等于这个回文串长度 2 + 1相等

于是就转换成如何快速求出p数组

利用回文串对称性扩展回文串，p[i]不在直接赋值为1，而是根据之前求出的p[j]， 0 < j < i

用mx表示所有字串产生的最大回文子串的最大右边界，Id表示产生这个最大右边界的对称轴的位置。

实现

分类讨论

• 情况 1 i < mx 利用回文串性质，对于i,可以找到一个关于id对称的位置 j = id * 2 - i，惊醒加速查找。 而次情况有分为三种情况。

  • 1.1

  此时o[i] = p[j] 此时，串i可以再向两边扩张，如果可以向两边扩张，p[j]也可以，而p[j]已经确定了，所以串i不想两边扩张。

  • 1.2

  此时p[i] = p[j] 但是串i可以再向两边扩张。 一看就知道。但是看不到

  -1.3

  此时p[i] = mx - i 此时只确定i在mx以内的部分回文，并不能确定串i和串j相同。所以不能往外扩张.

  • 情况2 i >= mx

  之前记录的用不上了，所以p[i] = 1;

模版：

int init(){//初始化 
    int len = strlen(s);
    str[0] = '@';
    str[1] = '#';//@防止数组越界，#添加字符
    int j = 2;
    for(int i = 0; i < len; i ++){
        str[j ++] = s[i];
        str[j ++] = '#';
    }
    str[j] = '\0';
    return j;
}

int manacher(){
    int ans = -1, len = init(), mx = 0, id = 0;//mx为右边界
    for(int i = 1 ; i < len; i ++){
        if(i < mx)
            p[i] = min(p[id * 2 - i], mx - i);
        else
            p[i] = 1;
        while(str[i + p[i]] == str[i - p[i]])
            p[i] ++;
        if(p[i] + i > mx){
            mx = p[i] + i;
            id = i;
        }
        ans = max(ans, p[i] - 1);
    }
    return ans;
}