Martian148's blog Martian148's blog
首页
  • ICPC 算法笔记
  • ICPC 算法题解
  • 体系结构
  • 高等数学
  • 线性代数
  • 概率论与数理统计
  • 具体数学
  • Martian148的奇思妙想
  • 游记
  • 通识课笔记
关于
  • useful 网站
  • 友情链接
  • 分类
  • 归档

Martian148

一只热爱文科的理科生
首页
  • ICPC 算法笔记
  • ICPC 算法题解
  • 体系结构
  • 高等数学
  • 线性代数
  • 概率论与数理统计
  • 具体数学
  • Martian148的奇思妙想
  • 游记
  • 通识课笔记
关于
  • useful 网站
  • 友情链接
  • 分类
  • 归档
  • 线上赛板子(实时更新)
  • 数据结构

  • 数学

  • 计算几何

  • 动态规划

  • 图论

  • 字符串

    • KMP
    • Manacher
      • 引入
      • 实现
  • 杂项

  • 算法笔记
  • 字符串
martian148
2024-09-03
目录

Manacher

# Manacher

# 引入

Manacher 算法可以在 O(n)O(n)O(n) 的时间内求出一个字符串中的最长回文串

先需要改造原字符串,在字符之间和两端插入 #,改造后,都变成了奇回文串,并把 s[0]s[0]s[0] 改成 $

那么,aba 就改造成 $#a#b#a# 了

我们定义回文半径 d[i]d[i]d[i] 表示以 iii 为中心的最长回文串的长度的一半,叫回文半径

image.png

加速盒子 [l,r][l,r][l,r],算法过程中我们维护右端点最靠右的最长回文串,利用盒子,借助之前的状态来加速计算的状态,具体的来说,盒内的 d[i]d[i]d[i] 可以利用对称点的 ddd 值来转移,盒外暴力

# 实现

计算前 i−1i-1i−1 个 ddd 函数,维护盒子 [l,r][l,r][l,r]

  1. 如果 i≤ri \le ri≤r ,则 iii 的对称点为 r−i+lr-i+lr−i+l
    • 若 d[r−i+1]<r−i+1d[r-i+1]<r-i+1d[r−i+1]<r−i+1 ,则 d[i]=d[i−l+1]d[i]=d[i-l+1]d[i]=d[i−l+1]
    • 若 d[r−i+1]≤r−i+1d[r-i+1]\le r-i+1d[r−i+1]≤r−i+1 ,则令 d[i]=r−i+1d[i]=r-i+1d[i]=r−i+1,从 r+1r+1r+1 往后暴力枚举
  2. 如果 i>ri>ri>r ,则从 iii 开始暴力枚举
  3. 求出 d[i]d[i]d[i] 后,如果 i+d[i]−1>ri+d[i]-1>ri+d[i]−1>r ,则更新盒子 l=i−d[i]+1,r=i+d[i]−1l=i-d[i]+1,r=i+d[i]-1l=i−d[i]+1,r=i+d[i]−1
auto manacher(string a) {
    string s = "$#";
    for (int i = 0; i < a.size(); i++) 
        s += a[i], s += '#';
    vector<int> d(s.size());
    d[1] = 1;
    for (int i = 2, l, r = 1; i < s.size(); i++) {
        if (i <= r) d[i] = min(r - i + 1, d[r - i + l]);
        while (s[i - d[i]] == s[i + d[i]]) d[i] ++;
        if (i + d[i] - 1 > r) 
            l = i - d[i] + 1, r = i + d[i] - 1;
    }
    return d;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
上次更新: 2025/04/08, 18:03:31
KMP
01分数规划

← KMP 01分数规划→

最近更新
01
Java基础语法
05-26
02
开发环境配置
05-26
03
pink 老师 JavaScript 学习笔记
05-26
更多文章>
Theme by Vdoing | Copyright © 2024-2025 Martian148 | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式