初见 | 字符串 | Manacher

2024-01-13 22:05:22

前言

学这个的主要原因是学完比较初步的网络流之后有点不知道该学啥，看到旁边 Dfkuaid 因为要去 ZR 氪金而恶补字糊串，于是我就跟着他博客学一学罢。（所有这里有很多东西都是搬过来的（bushi——）

PS:在写本文的时候 HD 的情绪极其不稳定，所以可能出现一些迷惑言论，以及一些神毕标题。
（要怪就怪某个 [数据销毁] 的 [数据销毁] .---)

抛出问题！

给定一个长度为 \(n\) 的字符串 \(s\)，求其最长回文子串。

举例：设 \(s=\tt{abcdkdca}\)，则其最长回文子串为 \(\tt{cdkdc}\)，长度为 \(\tt{5}\)。

BF 解决方案

看到这个题之后我们能够大致判断出来在最坏情况之下，时间复杂度是 \(O(n^2)\) 的。

考虑到回文串的性质，我们朴素的想法就是枚举一个中心 \(i\) 然后不断的扩张两端直到不符合回文串的要求。

然后有伪代码如下：（对 Dfkuaid 的伪代码略作修改）[1]

\[\begin{aligned} &\text{Function : }\tt{Checker}(a,b,s)\&1.\ \quad\text{If } a\geqslant0\texttt{ and }b<length(s)\&2.\ \quad\qquad\text{then return }true\&3.\ \quad\qquad\text{else return }false\\&\&\text{Procedure ：}\ \tt{Brute\ Force}(s:string)\&1.\ \quad ans\gets 0\&2.\ \quad\text{For }i\gets0\text{ to }length(s)-1\&3.\ \quad\qquad\text{do }j\gets0\&4.\ \quad\qquad\text{While }\tt{Checker}(i-j,i+j,s)\texttt{ and }s[i-j]=s[i+j]\&5.\ \quad\qquad\qquad\text{do }ans\gets\max\{ans,2\times j+1\}\&6.\ \quad\qquad\text{End While}\&7.\ \quad\text{End For}\\end{aligned} \]

大概这就是第一眼看到这个问题之后的所有朴素想法了罢，感觉这个 BF 做是 \(O(n^2)\) 的问题貌似也没有什么线性复杂度的做法。

但是她有！那就是本文的主题：\(\tt{Manacher}\).

Manacher

在说 Manacher 之前，我们先进一步研究回文串的性质。

进一步透掉回文串！

我们来考虑一个回文串到底是可以用什么样的信息来表示。

来回望一下上面的 BF 过程，因为回文串是对称的，所以我们主要关注的就是中心和半径长度，于是乎我们就从这里下手去表示一个回文串。

首先我们注意到奇数串的中心是一个确切的在字符串中的位置，而偶数串的中心是在两个位置之间，无法统一的来表示。

于是我们就考虑如何进行一些神妙操作之后把偶数串和奇数串统一起来，于是我们就迎来了 Manacher 算法的第一步。

把她变成你想要的样子！

实际上很简单，我们只需要原有的字符串的基础上进行一个简单的修改即可：在字符串的开头和结尾以及每两个字符之间都加上一个无关字符。

由于大部分的字符串问题都是和字母 & 数字相关，于是这里的无关字符我就采用的是 #。

这一步操作之后，不管你原来字符串里的回文串是奇数串还是偶数串，都变成奇数串的样子了（

比如 abdfettefdb 就变成了 #a#b#d#f#e#t#t#e#f#d#b#，原串的最大回文子串是 bdfettefdb，是一个偶数串，而现在就是 #b#d#f#e#t#t#e#f#d#b#，这是一个奇数串。

同时，为了方便我们枚举半径长度而不越界，我们可以在进行完上述操作之后的新字符串上再进行一次操作：在字符串的头和尾再加上两个互不相同的无关字符。

这里选取的是 $ 和 ^。

于是上面那个串就变成了 $#a#b#d#f#e#t#t#e#f#d#b#^。

于是乎我们就把字符串的格式都统一了起来，然后就可以进行神毕的操作了！

定义一些东西......

  • 定义 p[i] 为以 i 为中心的最长回文串长度。

  • 定义 id 表示当前位置加上该位置最长回文半径可覆盖的范围最远的位置。[1]（感性理解一下，不知道该怎么形容更加合适，推荐结合下面的代码手摸摸理解）

  • 定义 mx 表示 id 加上 p[id] 之后的距离，也就是以 id 为中心最长的回文串的右边界。

然后如何操作 ?

先把上图的所有东西都在这里放出来罢：

初见 | 字符串 | Manacher[1]

如果如上图一样，我们假定枚举的 i < mx ，那么以 i 为中心的回文串只有如下两种情况：

  1. 完全被 mx 的对称点和 mx 包含。

  2. 右端超出 mx 的范围。

假设我们是从左到右有序枚举的 i，那么 i 关于 id 的对称点 i‘ 的 p[i‘] 显然是已经求出的。

而我们根据 mx 和 id 的定义又能知道 mx 的对称点 mx‘ 为边界构成的字符串必然是一个回文串。

因为对于我们枚举到 i 的时候，i‘ 和 id 的各项数据我们都是已经求出的，于是我们可以借助 它们来继续合理接续。

如下图，若以 i‘ 为中心的最长回文串的左端不能够到达 mx‘ ，那么以 i 为中心的最长回文串也一定不会覆盖 mx。

初见 | 字符串 | Manacher[1]

反之，若其左端超过了 mx‘，那么 i 的回文串的右端不会超出 mx。

如下图，紫红涩的那一段一定不是相同的，因为如果她们相同，mx 还能继续向右扩展，这与 mx 的定义相悖，所以 那么 i 的回文串的右端不会超出 mx。

初见 | 字符串 | Manacher[1]

剩下的就是其左端和 mx‘ 重合的情况，那么显然如下图一样 p[i] 可以继续伸展。

初见 | 字符串 | Manacher[1]

于是就有如下核心代码：

        if(i<mx) p[i]=Hmin(p[(id<<1)-i],mx-i);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]) ++p[i];
        if(i+p[i]>mx) id=i,mx=i+p[i];

你要的 Code ！

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#define Heriko return
#define Deltana 0
#define Romanno 1
#define S signed
#define LL long long
#define R register
#define I inline
#define CI const int
#define mst(a, b) memset(a, b, sizeof(a))
#define ON ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

template<typename J>
I J Hmin(const J &x,const J &y) {Heriko x<y?x:y;}

template<typename J>
I J Hmax(const J &x,const J &y) {Heriko x>y?x:y;}

CI MXX=2.3e7;

int ans,p[MXX],l;

char org[MXX],s[MXX];

I void Into()
{
    s[l++]=‘$‘,s[l++]=‘#‘;
    while(cin>>s[l]) s[++l]=‘#‘,++l;
    s[l++]=‘^‘,s[l]=‘\0‘;
}

I void Manacher()
{
    int id(0),mx(0);
    for(R int i=0;i<l;++i)
    {
        if(i<mx) p[i]=Hmin(p[(id<<1)-i],mx-i);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]) ++p[i];
        if(i+p[i]>mx) id=i,mx=i+p[i];
        ans=Hmax(ans,p[i]-1);
    }
}

S main() {ON;Into();Manacher();cout<<ans;Heriko Deltana;}

复杂度相关

因为在计算一个特定位置的答案时我们总会运行朴素算法，所以一眼看去该算法的时间复杂度为线性的事实并不显然。

然而更仔细的分析显示出该算法具有线性复杂度。此处我们需要指出，计算 Z 函数的算法 和该算法较为类似，并同样具有线性时间复杂度。

实际上，注意到朴素算法的每次迭代均会使 \(\tt{r}\) 增加 1 ，以及 \(\tt{r}\) 在算法运行过程中从不减小。这两个观察告诉我们朴素算法总共会进行 \(O(n)\) 次迭代。

Manacher 算法的另一部分显然也是线性的，因此总复杂度为 \(O(n)\) 。[2]

因此 \(\tt{Manacher}\) 是很优秀的字符串算法的说~

End

中间的文字描述我尽力了，不过还是建议学字糊串的时候多手摸摸（

参考资料

初见 | 字符串 | Manacher

上一篇：thymeleaf多重${}


下一篇：基础问答【一】