[最长回文字符串]manacher马拉车

技术分享 3年前 (2023-07-15) 0 999+

manacher马拉车 https://www.luogu.com.cn/problem/P3805

闲言一下：花了一个中午终于把 manacher 给搞懂了。本文将以一个蒟蒻的身份来，来写写马拉车算法。首先请自行回顾暴力的最长回文字符串算法。首先我们将通过枚举中心点，并扩展以该中心点为回文中心的回文串长度的算法称为 “中心扩展法”。manacher算法便是以“中心扩展法”为核心，利用枚举中获取的信息优化而来的。

具体地来说：

首先在解决奇偶回文字符串时，我们使用分类讨论的方法，解决了奇数和偶数的问题，但是这样未免过于麻烦，有什么可以将二者统一的方式呢？

这是处理前的字符串

具体地来说：

首先在解决奇偶回文字符串时，我们使用分类讨论的方法，解决了奇数和偶数的问题，但是这样未免过于麻烦，有什么可以将二者统一的方式呢？

这是处理前的字符串 a b b c 1 2 3 4   这是处理后的字符串 # a # b # b # c # 1 2 3 4 5 6 7 8 9

我们通过加字符的方法，注意这里不一定要是 # ，也可以是其他字符，主要目标是为了将奇偶回文字符串统一了起来。这样在处理回文字符串时，会更加的方便。（不过也容易犯一些粗心的小问题，这些问题会在文章末尾提及）。

接下来回想一下中心扩展法求解最长回文序列的时候。遇到这种情况时

a b a d a b a  1 2 3 4 5 6 7

当我们枚举完以下标为 4 的点为中心时，我们可以知道 1~7 为回文序列。加上前面以下标为3的点为中心时，我们可知道 1~3 为回文序列。根据回文序列的对称性，我们可以得出 5~7 也为回文序列。但在我们使用中心扩展法时，就需要多余地去枚举以下标为3的点为中心的回文半径的长度。这大大地浪费了时间。因此我们可以从这个角度入手，优化我们的算法。

从中心扩展法的基础上，再根据刚刚从特殊数据的角度，我们可以想到先定义几个变量maxr,mid ，用来表示当前已知的回文序列中最右的右端点，及该回文序列的中点。为什么要记录最右的右端点呢？因为右端点越右的回文序列就越容易包括后面还未遍历的中心，这样就能尽可能的达到，通过现有信息尽可能减少多余遍历的目的了。再定义一个数组 p[i] 表示以 i 为中点的回文序列的回文半径。

具体来讲一下优化的要点，

情况一

a b b c 
1 2 3 4 

这是处理后的字符串 
# a # b # b # c # 
1 2 3 4 5 6 7 8 9

接下来回想一下中心扩展法求解最长回文序列的时候。遇到这种情况时

a b a d a b a  1 2 3 4 5 6 7

具体来讲一下优化的要点，

情况一

如果是上图的这种情况，则p[i]=p[j] ， j=mid-(i-mid) --> j=2*mid-i 。（回文序列的对称性）

情况二

如果是上图的这种情况，则不一定p[i]=p[j] ，因为超过ml ~ mr的部分并不满足回文序列的性质。所以只有在ml ~ mr的部分才能进入计算，因此p[i]=mr-i+1 。

重要的优化只有这些，其他的和中心扩展法的做法大致相同。

#include<bits/stdc++.h> using namespace std; const int N=9*1e7; string str="!#",c;/*为什么第一位是“！”？                     为了避免程序第16行扩展时越界 */  int p[N],mid=0,mr=0,ans;  void work(){     cin>>c;      for(int i=0;c[i]>='a'&&c[i]<='z';i++){         str+=c[i];         str+='#';     }/*处理原序列*/      for(int i=1;i<str.size();i++){         if(i<=mr) p[i]=min(p[2*mid-i],mr-i+1);         /*i关于mid对称点; mid-（i-mid）——> 2*mid-i  */          while(str[i-p[i]]==str[i+p[i]]) p[i]++;         //这里其实就是扩展 回文序列的 回文半径          if(i+p[i]>mr){             mid=i;             mr=i+p[i]-1;          }         if(p[i]>ans) ans=p[i];      }     cout<<ans-1; } int main(){     work();     return 0; }