马拉车学习笔记
title: 马拉车学习笔记
categories:
- ICPC
tags:
- null
abbrlink: 2e68fff1
date: 2023-05-29 00:00:00
马拉车学习笔记
概念与定义:
回文串:S=R(S)
回文中心:
- 奇长度:回文中心为$S[\frac{n+1}{2}]$,如$abcba$
- 偶长度:回文中心在$S[\frac{n}{2}]与S[\frac{n}{2}+1]$之间,如$ abc|cba$。
回文半径L:回文中心到回文串左右端点的距离,常用二元组$< 回文中心,回文半径>$来表示一个回文子串.
回文长度和回文半径的关系:
- 奇长度回文串:$|S|=2L-1$
- 偶长度回文串:$|S|=2L$
回文半径的二分性:回文半径-1 等价于同时删掉回文串的首尾字母,依然是回文串。
回文串和 Border:对于回文串 S,回文前(后)缀等价于Border。因此得到结论:回文串的回文前后缀都是border(!!!)
算法预处理:为了将偶回文串的处理方式与奇回文串统一起来,将 S 的每两个字母中间,以及开头结尾插入 。
- 因此所有回文串都变成奇数长度,且首尾一定是 #。
- 所有极长回文子串长度一定为奇数:因为极长回文子串一定以 #开头结尾。
P[i] 表示以 i 为回文中心的最大回文半径。
板子:传入$0base$即可
struct PAS {
string s = "#";
int len = 1;
vector<int> p;
// vector<pair<int, int>> all;
PAS() {}
PAS(string t) {
for (auto c : t) {
s += c;
s += '#';
len += 2;
}
s = " " + s;
p.resize(len + 1);
getp(s);
}
vector<int> getp(string t) {
int mid = 0, r = 0;
for (int i = 1; i <= len; i++) {
if (i > r)
p[i] = 1;
else
p[i] = min(p[2 * mid - i], r - i + 1);
while (i - p[i] > 0 && i + p[i] <= len && t[i - p[i]] == t[i + p[i]]) {
p[i] += 1;
// int ql, qr;
// if ((i - p[i] + 1) % 2 == 0)
// ql = (i - p[i] + 1) / 2;
// else
// ql = (i - p[i] + 2) / 2;
// if ((i + p[i] - 1) % 2 == 0)
// qr = (i + p[i] - 1) / 2;
// else
// qr = (i + p[i] - 2) / 2;
// all.emplace_back(ql, qr);
}
if (i + p[i] - 1 > r)
mid = i, r = i + p[i] - 1;
}
return p;
}
int getmax() {
int ans = 0;
for (int i = 1; i <= len; i++) {
ans = max(ans, p[i]);
}
return (ans - 1);
}
};
复杂度分析:每次暴力匹配一定伴随着最右回文串右端点 R 的右移。因此复杂度为线性。
用法:
求每个回文中心的回文半径
求本质不同回文串:在 $Manacher$ 中,新的回文串一定出现在使得最右串右移的时候。因此本质不同回文串至多 $n $个,把所有更新最右回文串去重即得到本质不同回文串
下标映射关系:首先我们预处理过的字符串是1base的,所有有效字符都是偶数,那么对应原字符串下标就是$\left \lfloor \frac{i}{2} \right \rfloor $.
- 对于无效字符串我们需要知道他右区间的第一个有效字符下标是$\left \lfloor \frac{i+1}{2} \right \rfloor $,左区间的第一个有效字符下标是$\left \lfloor \frac{i-1}{2} \right \rfloor $,这在前缀和差分统计回文串某些数量信息时有用
P3805 【模板】manacher - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
void solve()
{
string s;
cin >> s;
PAS pas(s);
cout << pas.getmax() << endl;
}
Gym10198-Mediocre String Problem-2018南京ICPC现场赛 - Cwolf9 - 博客园 (cnblogs.com)
https://acm.hdu.edu.cn/showproblem.php?pid=6599
例题:
1.https://codeforces.com/problemset/problem/17/E题意:找出所有位置相交的回文串的对数。
Sol:考虑容斥,所有回文串的对数减去不相交的回文串对数。
- 回文串的对数容易统计,我们只需要映射回原字符串下标后,每次计算长度就可以。
- 对于不相交的字符串,我们考虑枚举分割点,也就是第一个回文串的结束的位置。
- 我们想知道有多少回文串以这个位置作为右端点:我们差分维护,最后求一遍前缀和
- 有多少个回文串的起左端点严格大于当前位置:同样也是差分维护,前缀和统计,严格大于的贡献用后缀和即可
void solve(){
cin>>n;;
string s;
cin>>s;
PAS pas(s);
int len=pas.len;
int res=0;
vector<int>pre(n+2),suf(n+3);
for(int i=1;i<=len;i++){
int rad=pas.p[i];
//右端点结束
int l=(i+1)/2,r=(i+rad-2)/2;
pre[l]++;pre[r+1]--;
//左端点开头
l=(i-rad+2)/2,r=i/2;
suf[l]++;suf[r+1]--;
res+=r-l+1;
res%=mod; //不能提前取模算贡献
}
for(int i=1;i<=n;i++){
pre[i]+=pre[i-1];pre[i]%=mod;
suf[i]+=suf[i-1];suf[i]%=mod;
}
suf[n+1]=0;
for(int i=n;i>=1;i--){
suf[i]+=suf[i+1];
suf[i]%=mod;
}
// cerr<<res<<endl;
//mod的不是质数,不能直接快速幂求逆元
if(res&1){
res=(res-1)/2%mod*(res%mod)%mod;
}
else {
res=res/2%mod*((res-1)%mod)%mod;
}
// res=res*(res-1)/2;
int tmp=0;
for(int i=1;i<=n-1;i++){
tmp+=pre[i]*suf[i+1]%mod;
tmp%=mod;
}
res=(res-tmp+mod)%mod;
cout<<res<<endl;
}
很多细节:1.这里取mod是51123987,不是质数,不能简单的快速幂得到逆元。但是大数乘法要取模又必须处理,考虑$x(x-1)/2$的时候奇偶性分讨一下。
2.这里取模必须手动取三次,不然会爆longlong
res=(res-1)/2%mod*(res%mod)%mod;
3.后缀和要多开一个空间,但差分的时候修改了那个无效空间,所以要清0.
2.https://www.luogu.com.cn/problem/UVA11475题意:给定一个字符串,问至少在结尾添加几个字符后字符串变成回文串?
Sol:考虑最差情况原串反转拼接,所以在马拉车处理的串中,这个题目答案串的中心点也是在范围内的。我们枚举答案的中心点,显然如果不是回文后缀无法作为备选答案,在备选答案中找到前缀最短的即可,找到后反转输出
string s;
void solve()
{
PAS pas(s);
int ans = inf;
n = pas.len;
for (int i = 1; i <= n; i++)
{
if (i + pas.p[i] - 1 == n)
ans = min(ans, (i - pas.p[i]) / 2);
}
string res = s;
for (int i = ans; i >= 1; i--)
res += s[i - 1];
cout << res << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// freopen("debug.txt", "w", stderr);
// int t=1;
// cin>>t;
while (cin >> s)
solve();
return 0;
}
3.https://acm.hdu.edu.cn/showproblem.php?pid=3948题意:给定字符串,求本质不同回文子串个数.
Sol:这是回文自动机的基本应用,这里用马拉车+字符串哈希求出。在马拉车右边界拓展的过程中,我们考虑记录左右端点,这是答案备选集,哈希提前预处理,每次存到set里即可。
void solve() {
string s;
cin >> s;
PAS pas(s);
Hash hs(s);
s = " " + s;
auto &v = pas.all;
set<pii> st;
for (auto [x, y] : v) {
// cerr<<x<<" "<<y<<endl;
st.insert(hs.getpre(x, y));
}
cnt++;
cout << "Case #" << cnt << ": ";
cout << st.size() << endl;
}