最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

Manacher算法学习笔记

来源：博客园


(资料图)

Manacher算法是什么

Manacher算法就是马拉车。Manacher算法就是用于解决回文子串的个数的。

问题引入

P3805:【模板】manacher 算法

题目大意

给出一个只由小写英文字符 \(\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z\) 组成的字符串 \(S\) ,求 \(S\) 中最长回文串的长度。

算法

记录

为了找到最长的回文串的长度，我们首先就要考虑如何去把每一个回文串表示出来。因为是回文的，所以我们可以用 \(p_i\) 来表示。其中 \(i\) 表示回文串的中心，\(p_i\) 表示以第 \(i\) 个字符为中心的回文串的最长的回文串的半径。但是这样我们只能表示奇数长度的回文串，而偶数回文串就不能解决。

算法推到

但是一个 \(S\) 的回文串个数最坏可能是 \(n^2\) 级别的，会 TLE。那么我们该如何快速得到每个以 \(i\) 为中心的最长的长度呢？就像做 DP 题目一样，考虑类似 DP 的转移。考虑如何通过 \(p_i\) 来得到 \(p_{i+1}\)。我们用一幅图来生动形象的体会一下：这里我们就可以清晰的看到通过 \(p_i\) 得到 \(p_{i+1}\) 的两种。

  • 当 \((i-1)-q_{i-1}+1>i-q_i+1\) 时，即以 \(i-1\) 为中心的回文串被 \([i-p_i+1,i+p_i-1]\) 所包含在内。
  • 当 \((i-1)-q_{i-1}+1\le i-q_i+1\) 时，即以 \(i-1\) 为中心的回文串并没有被 \([i-p_i+1,i+p_i-1]\) 所包含在内。

第一种情况是很好办的，因为 \(i+1\) 与 \(i-1\) 以 \(i\) 为中心对称，直接 \(p_{i+1}=p_{i-1}\)。但是第二种情况就不好解决了，因为这就意味着我们似乎是要在继续判断 \(p_{i+1}\) 的最大值，好像如果运气不好的话时间复杂度就会达到 \(O(n^2)\)。这时就需要考虑单调性了，\(i\) 就可以不是 \(i+1\) 的前一个点，而可能是在 \(1\sim i\) 中的一个点。想象一下，当出现第二种情况时，\(i+1\) 就必须要用 \(O(n)\) 来暴力得到 \(p_{i+1}\)，但是如果 \(p_{i+1}\) 覆盖了整个 \([1,n]\) 的话，后面的 \(i+2\sim n\) 就都会被 \(p_{i+1}\) 所覆盖了。即可以直接 \(O(1)\) 得到答案，时间复杂度也就是 \(O(n)\)。所以我们可以得到结论，Manacher 的时间复杂度具有单调性，是单调不下降的。

实现

为了确保它的单调性，我们就需要一个 \(mid\) 来记录回文覆盖最大的点的下标，\(mx\) 为 \(mid\) 回文串的左端点。\(p_i\) 的初始值就是:

\[\begin{cases}1(i>mx) \\ \min(mx-i+1,p_{mid*2-i})(i\le mx)\end{cases}\]

在判断 \(a_{i+p_i}\) 是否与 \(a_{i-p_i}\) 相同，相同就扩张 \(p_i\)。然后在尝试用 \(i\) 去更新 \(mid,mx\) 就可以了。

Code

#include#define N 12000005#define int long longusing namespace std;int n,mx=1,mid,ans,p[N<<2];char a[N<<2],s[N<<1];signed main(){cin>>s+1;n=strlen(s+1);a[0]="$";a[1]="#";for(int i=1;i<=n;i++)a[i<<1]=s[i],a[(i<<1)+1]="#";n=(n<<1)+2;a[n]="@";for(int i=1;i<=n;i++){if(i<=mx)p[i]=min(mx-i+1,p[mid*2-i]);else p[i]=1;while(a[i+p[i]]==a[i-p[i]])++p[i];if(i+p[i]>mx)mx=i+p[i]-1,mid=i;ans=max(ans,p[i]);}cout<

关键词：