马年“码”上发力：用Manacher“马拉车”算法，拉平最长回文难题

💗博主介绍：计算机专业的一枚大学生 来自重庆 @燃于AC之乐✌专注于C++技术栈，算法，竞赛领域，技术学习和项目实战✌
💗根据博主的学习进度更新（可能不及时）
💗后续更新主要内容：C语言，数据结构，C++、linux（系统编程和网络编程）、MySQL、Redis、QT、Python、Git、爬虫、数据可视化、小程序、AI大模型接入，C++实战项目与学习分享。
👇🏻 精彩专栏 推荐订阅👇🏻
点击进入🌌作者专栏🌌：
算法画解 ✅
C++ ✅
🌟算法相关题目点击即可进入实操🌟
感兴趣的可以先收藏起来，请多多支持，还有大家有相关问题都可以给我留言咨询，希望希望共同交流心得，一起进步，你我陪伴，学习路上不孤单！

文章目录

• 前言
• Manacher（马拉车）算法
  • 问题：
  • 1.相关概念引入
  • 2.中心扩展算法
    • 算法原理
    • 预处理
  • 3.Manacher算法
    • 概念引入
    • 分类讨论（核心）
  • 4.算法模板
  • 结尾

前言

今年是马年， 我来分享一个与 “马” 有关的算法， Manacher(马拉车)。

算法如骏马，载我们驰骋于数据的原野。值此马年，愿各位的代码“码”不停蹄，一往无前，愿你们的项目“马”到功成，顺利上线，愿你们的Bug屈指可“马”，轻松搞定！新的一年，让我们驾驭技术的快马，共同奔赴星辰大海。

Manacher（马拉车）算法

问题：

1.在字符串中，找出所有的回文子串；

2.在字符串中，找出最长的回文子串；

两个问题可以结合解决。

1.相关概念引入

1.回文字符串： 正着读和反着读都⼀样的字符串就是回⽂字符串。

2.回文子串： 一个字符串的某个字串是回文。

3.奇回文串： 回文串的字符数为奇数。

4.偶回文串： 回文串的字符数为偶数。

5.回文中心： c, 回文串最中心的位置。 奇回文串（回文中心）： n + 1 / 2; 偶回文串（回文中心）： n / 2与n/2 + 1之间

6.回文半径： d, 回文中心到回文半径左/右端点的距离（字符数，包括本身）。

2.中心扩展算法

算法原理

1.从前往后遍历字符串，以 s[i] 或 s[i] 与 s[i + 1] 的中间作为回文串的中心位置；

2.从中间位置开始，枚举半径长度，逐渐向两边扩展，找出以该点为中心的最长的回文子串。

预处理

为了防止对奇偶回文字串进行分类讨论，且奇回文字串更好处理，这里将其统一转化为奇回文串。

预处理字符串：

在相邻字符之间和整个字符串的两端任意加⼊⼀个字符 ‘#’ 。

例如，字符串 s = “abcbaa” 经过预处理之后就变成： s = “#a#b#c#b#a#a#” 。

经过预处理之后：

本来是奇回⽂串，处理之后依旧是奇回文串。例如 “bab” 处理后为 “#b#a#b#” ；

本来是偶回⽂串，处理之后就变成奇回文串。例如 “abba” 处理后为 “#a#b#b#a#” ；

此时，在处理之后的串上跑中心扩展算法时，由于所有的回文串都是奇回文串，仅需枚举所有中心点，即可找到所有的回文串。

注意： （不用像 kmp 算法那样，加⼊⼀个不会出现的字符，这⾥可以加⼊任意字符。

因为判断回⽂的时候，只会原始字符和原始字符判断，新加⼊的字符和新加⼊的字符判断。因此，可以加入任意字符。）

代码：

string t, s;int m, n;// 以求解最⻓回⽂⼦串为例intfun(){// 预处理字符串 cin >> t; m = t.size(); s +=' ';//这里要处理边界不同，‘ ’ ！= ‘#’for(auto ch : t){ s +='#'; s += ch;} s +="##"; n = s.size()-2;int ret =1;// 中⼼扩展算法for(int i =1; i <= n; i++){int d =1;// 枚举向右向左的距离while(s[i - d]== s[i + d]) d++; ret =max(ret, d -1);}return ret;}

时间复杂度：O(n ^ 2 )

3.Manacher算法

概念引入

1.回文半径数组： d[i] (以i为中心的最长回文半径)。
例如，字符串“#a#a#a#b#a#", 回文半径数组：

2.两个重要的性质：

1.回文串的长度为d[i] - 1;

2.以i为中心的回文串有d[i] / 2 个。

3.加速盒子（最右回文串）：

从前往后填表的过程中，区间 [l, r] ,找到右端点最靠右的回文子串，不断维护区间。

它可以帮助我们加速填表。

如：“#a#a#a#b#a#”；

依次维护的区间：[1, 1] -> [1, 3] -> [1, 5] -> [1, 7] -> [1, 7] -> [1, 7] -> [1, 7] -> [5, 11] -> [5, 11]

4.【Manacher 算法 - 利⽤最右回文串加速更新回文半径数组】

分类讨论（核心）

从前往后填表，当填到d[i]时，d[1] ~ d[i - 1] 均已经填好，并且维护最右回文串[l, r] 。当填写时，分下面大类，四种情况讨论：

1. i > r, 当前点没有在最右回⽂串中。此时，d[1] ~ d[i - 1] 的回文信息提供不了任何帮

助。直接以 i 为中心暴力扩展（与中心扩展算法⼀致）；

2. i <= r, 当前点在最右回文串中，由对称性可知， j - l = r - i, 对称点j = r - i + l 的回文半径d[j], 分为一下三种情况进行讨论：

a. d[j] < r - i + 1（ 最长回文半径），即以 j 为中心的最长回文串包含在[l, r]内:

由对称性可知，d[i] = d[j] = d[r - i + l]

b. d[j] > r - i + 1，即以 j 为中心的最长回文串的左边界越过了l:

d[i] = r - i + 1。

c. d[j] = r - i = 1， 即以 j 为中心的最长回文串的左边界正好在l位置：

此时d[i]至少为d[j],且还可能往外扩展。 就可以从d[j]开始， 用中心扩展算法暴力向外扩展。

注意这里：1和2.c情况还会涉及到对最右回文串区间[l, r]的更新。

时间复杂度： 注意到，在整个算法执⾏的过程中 r 是不会回退的，相当于 i, r 两个指针不回退的向后移动。

因此整个时间复杂度为 O(n) 。

代码实现：

这里非常的精妙，可以把4种情况都考虑进去。

string t, s;int n, d[N];//预处理voidinit(){ cin >> t; s =' ';for(auto ch : t){ s +='#'; s += ch;} s +="##"; n = s.size()-2;}voidget_d(){ d[1]=1;for(int i =2, l =1, r =1; i <= n; i++){int len = r >= i ?min(d[r - i + l], r - i +1):1;//=1是第1种情况， d[r - i + 1]是第2，r - i + 1是第3，两个相等，任取一个是第4。while(s[i + len]== s[i -len]) len++;//1，4会进入循环，执行中心扩展算法， 2，3会判断不等if(i + len -1> r) r = i + len -1, l = i - len +1;//更新区间 d[i]= len;}}

4.算法模板

P3805 【模板】Manacher

代码：

#include<iostream>usingnamespace std;constint N =2.2e7+10; string t, s;int m, n;int d[N];intmain(){ cin >> t; m = t.size(); s +=' ';for(auto ch : t){ s +='#'; s += ch;} s +="##";//处理边界要不同 n = s.size()-2; d[1]=1;int ret =1;for(int i =2, l =1, r =1; i <= n; i++)// 这里初始化，不能在内 {int len = r >= i ?min(d[r - i + l], r - i +1):1;while(s[i + len]== s[i - len]) len++;if(i + len -1> r) r = i + len -1, l = i - len +1; d[i]= len; ret =max(ret, d[i]-1);} cout << ret << endl;return0;}

结尾

愿你的程序一马平川，运行无阻；
愿你的思路天马行空，创意无限；
愿你的职场骏马奔腾，前程似锦！
码上成功，我们马上同行！🐎

看到这里请点个赞，关注，如果觉得有用就收藏一下吧。后续还会持续更新的。 创作不易，还请多多支持！