浅谈马拉车
马拉车其实挺好理解的，写篇博客以便复习。
正题
简介
Manacher主要的思想是回文串的对称性，即
- 在一个大回文串中,一定存在一个与\(X\)关于回文对称中心对称的子串\(Y\),故我们利用已知的回文串搞事情.
算法流程
-
考虑回文串有
ABA(对称中心为一个字符）和ABBA(对称中心为两个字符)两种情况,则每个字符间加一个特殊字符,成为|A|B|A|和|A|B|B|A|两种情况,此时都转成了对称中心为一个字符的情况. -
考虑记录一个\(p\)数组,\(p[i]\)表示以\(i\)为对称中心能向外拓展的最大的回文串的半径长度.
-
从左到右遍历字符串\(s\) , 过程中维护一个变量\(r\)，表示当前已知的回文串中右端点最靠右的右端点的下标,维护一个变量\(mid\),表示右端点最靠右的回文串的对称中心的下标.
-
枚举\(i\),若\(i\le r\),则考虑与\(i\)关于\(mid\)的对称点\(j = mid*2-i\) , 我们就已经找到一个现成的回文串,即\([j-p[j]+1,j+p[j]-1]\),需要注意的是,若\(p[j] > r-i+1\),则长度大于\(r-i+1\)的部分是不回文的,故\(p[i] = min(p[j],r-i+1)\).
-
考虑拓展回文,尝试更新\(r\)和\(mid\)。
时间复杂度分析
- 若\(p[j] < r-i+1\) , 则已经证明了第三步的拓展是不可能成功的,即\(p[i]\)就不会耗费时间拓展.
- 否则,考虑若向外拓展成功,每拓展一次\(r\)便会增加一,考虑\(r\)最多只会到\(n\),故时间复杂度为\(O(n)\).
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1.1e7+15;
int p[N<<1];
char a[N*2];
int read(){int tot;char ch = getchar();a[0]='@',a[tot=1]='|';//考虑在0处添加一个@,避免端点拓展时越界while(ch<'a'&&'z'<ch) ch = getchar();while('a'<=ch&&ch<='z') a[++tot] = ch , a[++tot] = '|' , ch = getchar();return tot;
}
int main(){int n = read();int ans = 0;for(int i = 1 , mid = 0 , r = 0 ; i<=n ; i++){if(i<=r) p[i] = min(p[(mid<<1)-i],r-i+1);while(a[i-p[i]]==a[i+p[i]]) ++p[i];if(i+p[i]-1>r) r = i+p[i]-1 , mid = i;ans = max(ans,p[i]);}cout<<ans-1;return 0;
}