差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:lgwza:manacher_算法 [2020/10/02 13:59]
lgwza 创建
+++ 2020-2021:teams:legal_string:lgwza:manacher_算法 [2020/10/02 14:12] (当前版本)
lgwza
@@ 行 3: / 行 3: @@
 ===== 描述 =====
-给定一个长度为 $n$ 的字符串 $s$，请找到所有对 $(i,j)$ 使得子串 $s[i...j]$ 为一个回文串。当 $t=t_{rev}$ 时，字符串 $t$ 是一个回文串（$t_{rev}$ 是 $t$ 的反转字符串）。
+给定一个长度为 $n$ 的字符串 $s$，请找到所有对 $(i,j)$ 使得子串 $s[i... j]$ 为一个回文串。当 $t=t_{rev}$ 时，字符串 $t$ 是一个回文串（$t_{rev}$ 是 $t$ 的反转字符串）。
 ===== 更进一步的描述 =====
@@ 行 9: / 行 9: @@
 显然在最坏情况下可能有 $O(n^2)$ 个回文串，因此似乎一眼看过去该问题并没有线性算法。
-但是关于回文串的信息可用 **一种更紧凑的方式** 表达：对于每个位置 $i=0...n-1$，我们找出值 $d_1[i]$ 和 $d_2[i]$。二者分别表示以位置 $i$ 为中心的长度为奇数和长度为偶数的回文串个数。
+但是关于回文串的信息可用 **一种更紧凑的方式** 表达：对于每个位置 $i=0... n-1$，我们找出值 $d_1[i]$ 和 $d_2[i]$。二者分别表示以位置 $i$ 为中心的长度为奇数和长度为偶数的回文串个数。
 举例来说，字符串 $s=\mathtt{abababc}$ 以 $s[3]=b$ 为中心有三个奇数长度的回文串，也即 $d_1[3]=3$： $$
@@ 行 52: / 行 52: @@
 </code>
 </hidden>
+===== Manacher 算法 =====
+这里我们将只描述算法中寻找所有奇数长度子回文串的情况，即只计算 $d_1[]$；寻找所有偶数长度子回文串的算法（即计算数组 $d_2[]$）将只需对奇数情况下的算法进行一些小修改。
+为了快速计算，我们维护已找到的最靠右的子回文串的 **边界** $(l,r)$（即具有最大 $r$ 值的回文串，其中 $l$ 和 $r$ 分别为该回文串左右边界的位置）。初始时，我们置 $l=0$ 和 $r=-1$。
+现在假设我们要对下一个 $i$ 计算 $d_1[i]$，而之前所有 $d_1[]$ 中的值已计算完毕。我们将通过下列方式计算：
+  * 如果 $i$ 位于当前子回文串之外，即 $i>r$，那么我们调用朴素算法。因此我们将连续地增加 $d_1[i]$，同时在每一步中检查当前的子串 $[i-d_1[i]... i+d_1[i]]$ 是否为一个回文串。如果我们找到了第一处对应字符不同，又或者碰到了 $s$ 的边界，则算法停止。在两种情况下我们均已计算完 $d_1[i]$。此后，仍需记得更新 $(l,r)$。
+  * 现在考虑 $i\le r$ 的情况。我们将尝试从已计算过的 $d_1[]$ 的值中获取一些信息。首先在子回文串 $(l,r)$ 中反转位置 $i$，即我们得到 $j=l+(r-i)$。现在来考察值 $d_1[j]$。因为位置 $j$ 同位置 $i$ 对称，我们 **几乎总是** 可以置 $d_1[i]=d_1[j]$。该想法的图示如下（可认为以 $j$ 为中心的回文串被“拷贝”至以 $i$ 为中心的位置上）：
+$$
+  \ldots\ \overbrace{ s_l\ \ldots\ \underbrace{ s_{j-d_1[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_1[j]-1} }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-d_1[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_1[j]-1} }_\text{palindrome}\ \ldots\ s_r }^\text{palindrome}\ \ldots
+$$
+然而有一个 **棘手的情况** 需要被正确处理：当“内部”的回文串到达“外部”回文串的边界时，即 $j-d_1[j]+1\le l$（或者等价地说，$i+d_1[j]-1\ge r$）。因为在“外部”回文串范围以外的对称性没有保证，因此直接置 $d_1[i]=d_1[j]$ 将是不正确的：我们没有足够的信息来断言在位置 $i$ 的回文串具有同样的长度。
+实际上，为了正确处理这种情况，我们应该“截断”回文串的长度，即置 $d_1[i]=r-i$。之后我们将运行朴素算法以尝试尽可能增加 $d_1[i]$ 的值。
+该种情况的图示如下（以 $j$ 为中心的回文串已经被截断以落在“外部”回文串内）：
+$$
+  \ldots\ \overbrace{ \underbrace{ s_l\ \ldots\ s_j\ \ldots\ s_{j+(j-l)} }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-(r-i)}\ \ldots\ s_i\ \ldots\ s_r }_\text{palindrome} }^\text{palindrome}\ \underbrace{ \ldots \ldots \ldots \ldots \ldots }_\text{try moving here}
+$$
+该图示显示出，尽管以 $j$ 为中心的回文串可能更长，以至于超出“外部”回文串，但在位置 $i$，我们只能利用其完全落在“外部”回文串内的部分。然而位置 $i$ 的答案可能比这个值更大，因此接下来我们将运行朴素算法来尝试将其扩展至“外部”回文串之外，也即标识为 "try moving here" 的区域。
+最后，仍有必要提醒的是，我们应当记得在计算完每个 $d_1[i]$ 后更新值 $(l,r)$。
+同时，再让我们重复一遍：计算偶数长度回文串数组 $d_2[]$ 的算法同上述计算奇数长度回文串数组 $d_1[]$ 的算法十分类似。
+## Manacher 算法的复杂度
+因为在计算一个特定位置的答案时我们总会运行朴素算法，所以一眼看去该算法的时间复杂度为线性的事实并不显然。然而更仔细地分析显示该算法具有线性复杂度。
+实际上，注意到朴素算法的每次迭代均会使 $r$ 增加 $1$，以及 $r$ 在算法运行过程中从不减小。这两个观察告诉我们朴素算法总共会进行 $O(n)$ 次迭代。
+Manacher 算法的另一部分显然也是线性的，因此总复杂度为 $O(n)$。
+===== Manacher 算法的实现 =====
+==== 分类讨论 ====
+为了计算 $d_1[]$，我们有以下代码：
+<hidden>
+<code cpp>
+vector<int> d1(n);
+for (int i = 0, l = 0, r = -1; i < n; i++) {
+  int k = (i > r) ? 1 : min(d1[l + r - i], r - i);
+  while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
+    k++;
+  }
+  d1[i] = k--;
+  if (i + k > r) {
+    l = i - k;
+    r = i + k;
+  }
+}
+</code>
+</hidden>
+计算 $d_2[]$ 的代码十分类似，但是在算术表达式上有些许不同：
+<hidden>
+<code cpp>
+vector<int> d2(n);
+for (int i = 0, l = 0, r = -1; i < n; i++) {
+  int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
+  while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
+    k++;
+  }
+  d2[i] = k--;
+  if (i + k > r) {
+    l = i - k - 1;
+    r = i + k;
+  }
+}
+</code>
+</hidden>
+==== 统一处理 ====
+虽然在讲解过程中及上述实现中我们将 $d_1[]$ 和 $d_2[]$ 的计算分开考虑，但实际上可以通过一个技巧将二者的计算统一为 $d_1[]$ 的计算。
+给定一个长度为 $n$ 的字符串 $s$，我们在其 $n+1$ 个空中插入分隔符 $\#$，从而构造一个长度为 $2n+1$ 的字符串 $s'$。举例来说，对于字符串 $s=\mathtt{abababc}$，其对应的 $s'=\mathtt{\#a\#b\#a\#b\#a\#b\#c}$。
+对于字母间的 $\#$，其实际意义为 $s$ 中对应的“空”。而两端的 $\#$ 则是为了实现的方便。
+注意到，在对 $s'$ 计算 $d_1[]$ 后，对于一个位置 $i$，$d_1[i]$ 所描述的最长的子回文串必定以 $\#$ 结尾（若以字母结尾，由于字母两侧必定各有一个 $\#$，因此可向外扩展一个得到一个更长的）。因此，对于 $s$ 中一个以字母为中心的极大子回文串，设其长度为 $m+1$，则其在 $s'$ 中对应一个以相应字母为中心，长度为 $2m+3$ 的极大子回文串；而对于 $s$ 中一个以空为中心的极大子回文串，设其长度为 $m$，则其在 $s'$ 中对应一个以相应表示空的 $\#$ 为中心，长度为 $2m+1$ 的极大子回文串（上述两种情况下的 $m$ 均为偶数，但该性质成立与否并不影响结论）。综合以上观察及少许计算后易得，在 $s'$ 中，$d_1[i]$ 表示在 $s$ 中以对应位置为中心的极大子回文串的 **总长度加一**。
+上述结论建立了 $s'$ 的 $d_1[]$ 同 $s$ 的 $d_1[]$ 和 $d_2[]$ 间的关系。
+由于该统一处理本质上即求 $s'$ 的 $d_1[]$，因此在得到 $s'$ 后，代码同上节计算 $d_1[]$ 的一样。
+===== 例题 =====
+[[https://www.luogu.com.cn/problem/P3805|P3805 【模板】manacher算法]]
+给出一个只由小写英文字符 $a,b,c,\cdots,y,z$ 组成的字符串 $S$，求 $S$ 中最长回文串的长度。字符串长度为 $n$。
+代码：
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=1.1e7+5;
+char Ma[N<<1];
+int Mp[N<<1];
+void Manacher(char s[],int len){
+	int l=0;
+	Ma[l++]='$';
+	Ma[l++]='#';
+	for(int i=0;i<len;i++){
+		Ma[l++]=s[i];
+		Ma[l++]='#';
+	}
+	Ma[l]=0;
+	int mx=0,id=0;
+	for(int i=0;i<l;i++){
+		Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
+		while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;
+		if(i+Mp[i]>mx){
+			mx=i+Mp[i];
+			id=i;
+		}
+	}
+}
+char s[N];
+int main(){
+	scanf("%s",s);
+	int len=strlen(s);
+	Manacher(s,len);
+	int ans=0;
+	for(int i=0;i<2*len+2;i++)
+		ans=max(ans,Mp[i]-1);
+	printf("%d",ans);
+	return 0;
+}
+</code>
+</hidden>
+[[https://ac.nowcoder.com/acm/contest/7817/A|ABB]]
+**题意**：在给定字符串 $s$ 的末尾添加尽可能少的字符，使其成为回文串。
+**题解**：等价于求解原字符串中以末尾字符结尾的最长回文子串。
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=4e5+5;
+char Ma[N<<1];
+int Mp[N<<1];
+void Manacher(char s[],int len){
+	int l=0;
+	Ma[l++]='$';
+	Ma[l++]='#';
+	for(int i=0;i<len;i++){
+		Ma[l++]=s[i];
+		Ma[l++]='#';
+	}
+	Ma[l]=0;
+	int mx=0,id=0;
+	for(int i=0;i<l;i++){
+		Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
+		while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;
+		if(i+Mp[i]>mx){
+			mx=i+Mp[i];
+			id=i;
+		}
+	}
+}
+char s[N];
+int main(){
+	int n;
+	scanf("%d",&n);
+	scanf("%s",s);
+	int len=n;
+	Manacher(s,len);
+	int ans=0;
+	for(int i=0;i<2*len+2;i++)
+		if(Mp[i]-1==((2*len+1)-i))
+			ans=max(ans,Mp[i]-1);
+	printf("%d",len-ans);
+	return 0;
+}
+</code>
+</hidden>
+[[https://www.luogu.com.cn/problem/P4555|P4555 [国家集训队]最长双回文串]]
+**题意**：输入长度为 $n$ 的串 $S$，求 $S$ 的最长双回文子串 $T$，即可将 $T$ 分为两部分 $X$，$Y$，$(|X|,|Y|\ge1)$ 且 $X$ 和 $Y$ 都是回文串。
+**题解**：做 Manacher 时维护以 $i$ 为结尾的最长回文子串的长度 $ll[i]$，和以 $i$ 为开头的最长回文子串的长度 $rr[i]$。
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=1e5+5;
+char Ma[N<<1];
+int Mp[N<<1];
+int ll[N<<1],rr[N<<1];
+void Manacher(char s[],int len){
+	int l=0;
+	Ma[l++]='$';
+	Ma[l++]='#';
+	for(int i=0;i<len;i++){
+		Ma[l++]=s[i];
+		Ma[l++]='#';
+	}
+	Ma[l]=0;
+	int mx=0,id=0;
+	for(int i=0;i<l;i++){
+		Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
+		while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;
+		if(i+Mp[i]>mx){
+			mx=i+Mp[i];
+			id=i;
+		}
+		ll[i+Mp[i]-1]=max(ll[i+Mp[i]-1],Mp[i]-1);
+		rr[i-Mp[i]+1]=max(rr[i-Mp[i]+1],Mp[i]-1);
+	}
+	for(int i=1;i<l;i+=2) rr[i]=max(rr[i],rr[i-2]-2);
+	for(int i=l-1;i>=1;i-=2) ll[i]=max(ll[i],ll[i+2]-2);
+}
+char s[N];
+int main(){
+	scanf("%s",s);
+	int len=strlen(s);
+	Manacher(s,len);
+	int ans=0;
+	for(int i=1;i<2*len+2;i+=2)
+		if(rr[i]&&ll[i])
+			ans=max(ans,ll[i]+rr[i]);
+	printf("%d",ans);
+	return 0;
+}
+</code>
+</hidden>
+===== 参考链接 =====
+[[https://oi-wiki.org/string/manacher/|OI Wiki]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具