manacher算法
斯♥哈♥学长的博客https://www.cnblogs.com/luckyblock/p/17044694.html#5140558
为什么老师叫他马拉车算法/yiw
简介
我们都知道，求最长回文子串可以枚举每一个开始的点，然后直接一个一个比较就完事，但这样的复杂度是接近
但是当我求出 \(p\) 数组的时候，我沉默了，两个的话不好找，所以考虑维护其他的东西。
既然我们是要求两相邻的回文串的最大长度，那么我们可以考虑维护一下以一个点为开始的回文串最大长度和以一个点为结尾的回文串最大长度，但是这就又有一个问题，就是当前点的字符是被算入了两个串里，考虑一下，我们在一开始插入了一些特殊字符，我们只要枚举这些特殊字符的不就好了吗！因为后面删去是不影响的。然后就是该如何维护，首先我们可以在求 \(p\) 的时候顺手维护一部分，因为当 \(i\) 为中点时，左端点为 \(i-p[i]+1\)，右端点为 \(i+p[i]-1\)，那么我们就可以先对这个求一个max，将其存放到 \(l\)，\(r\) 两个数组里面去，但是由于求 \(p\) 的时候都是最大的，所以导致一些短的回文串的开头结尾的数组没有存入，所以我们需要再推一遍，首先 \(r\) 是要倒着枚举的，因为是逐渐向左移，然后，当前的 \(r\) 数组有两种选择，一种是他的右一个字符的最大回文长度减一，因为中间插入了字符，在循环的时候是 \(i+=2\) 的，然后减去一也变成了减去二，下标也是 \(i+2\)，最后得出： \(r[i]=\max(r[i],r[i+2]-2)\)，\(l\) 数组同理可推得：\(l[i]=\max(l[i],l[i-2]-2)\)。然后最后遍历一遍所有的特殊字符对于 \(l[i]+r[i]\) 取一个 \(\max\) 就好啦！
#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n,p[N<<1],cnt,l[N<<1],r[N<<1],ans;
char s[N<<1];
signed main()
{
char c=getchar();
s[cnt]='~',s[++cnt]='%';
while(c<'a'||c>'z')c=getchar();
while(c>='a'&&c<='z')s[++cnt]=c,s[++cnt]='%',c=getchar();
s[cnt+1]=')';
int j=0,mid=0;
for(int i=1;i<=cnt;i++)
{
if(i<=j)p[i]=min(p[2*mid-i],j-i+1);
while(s[i-p[i]]==s[i+p[i]])p[i]++;
if(p[i]+i>j)j=p[i]+i-1,mid=i;
l[i-p[i]+1]=max(l[i-p[i]+1],p[i]-1);
r[i+p[i]-1]=max(r[i+p[i]-1],p[i]-1);
}
// cout<<"cao"<<endl;
for(int i=cnt;i>=1;i-=2)r[i]=max(r[i],r[i+2]-2);
for(int i=1;i<=cnt;i+=2)l[i]=max(l[i],l[i-2]-2);
for(int i=1;i<=cnt;i+=2)if(l[i]&&r[i])ans=max(l[i]+r[i],ans);
cout<<ans<<endl;
return 0;
}
P1659 [国家集训队]拉拉队排练
既然是求解回文串的问题，首先可以考虑一下 manacher 算法。
我发现题解中有的是直接在原串上跑 manacher，这样可以直接过滤掉长度为偶数的回文串，如果是要在修改后的串上跑 manacher 的话，我们在统计答案的时候可以直接特判一下，把是以原串里的字符为中心的回文串最大长度给算上，这样在原串里也是长度为奇数的回文串了。
对于排序的问题，我们可以开一个桶 \(t\) 数组来记录一下当前长度的回文串的数量，很容易发现，我们的 \(p[i]\) 里面存放的是以 \(i\) 为中心最大的回文半径，所以我们知道，像 \(abcdedcba\) 这种回文串，不仅只有这一个最长的，当去掉两头各一个字符时，就可以得到了另一个回文串 \(bcdedcb\)。
现在考虑如果处理以上的情况。如果是在往桶里面存放的时候用一个循环来一直减二修改的话，像一些以当前点为回文中心的字符串很长的情况就会 T 掉了，所以我们要用到类似于线段树的懒标记的方法，我们在将当前的回文串长度也就是 \(p[i]-1\) 放入桶中的时候，先不要急着给后面的也放入，等到了查询的时候，当前的 \(t[p[i]-1]\) 计算完了以后，我们再给 \(t[p[i]-1-2]\) 加上 \(t[p[i]-1]\) 的值，就相当于长度为 \(p[i]-1\) 的回文串全都去掉了两头各一个字符，变为了 长度为 \(p[i]-1-2\) 的回文串，这样可以使我们的复杂度大大降低，跑的也很快。
\(k\) 的范围较大，要用快速幂，同时注意取模和判无解。
#include<bits/stdc++.h>
#define int long long
#define P 19930726
#define N 1000010
using namespace std;
int n,k,p[N<<1],t[N<<1],cnt,maxn;
char s[N<<1];
inline int ksm(int x,int y)
{
int sum=1;
while(y)
{
if(y%2==1)
sum=(sum*x)%P;
x=(x*x)%P;
y=y>>1;
}
return sum%P;
}
signed main()
{
cin>>n>>k;
char c=getchar();
s[cnt]='!';s[++cnt]='%';
while(c<'a'||c>'z')c=getchar();
while(c>='a'&&c<='z')s[++cnt]=c,s[++cnt]='%',c=getchar();
s[cnt+1]='~';
int j=0,mid=0;
for(int i=1;i<=cnt;i++)
{
if(i<=j)p[i]=min(p[2*mid-i],j-i+1);
while(s[i+p[i]]==s[i-p[i]])p[i]++;
if(p[i]+i>j)j=p[i]+i-1,mid=i;
if(s[i]!='%')
{
int xx=p[i]-1;
t[xx]++;
maxn=max(maxn,p[i]-1);
}
}
// for(int i=1;i<=maxn;i++)
// cout<<t[i]<<" ";
// cout<<endl;
int ans=1,sum=0;
for(int i=maxn;i>=1;i--)
{
if(sum+t[i]>k)
{
ans=(ans*ksm(i,k-sum)%P);
sum+=t[i];
break;
}
sum+=t[i];
t[i-2]+=t[i];
ans=(ans*ksm(i,t[i])%P);
}
if(sum<k)
{
cout<<"-1"<<endl;
return 0;
}
cout<<ans<<endl;
return 0;
}
P9606 [CERC2019] ABB
不难发现最坏情况就是把前 \(n-1\) 个字符反转一下复制到后面。
发现后缀的回文串长度会使得添加的字符个数减少，例如样例三中 murderforajarof 实际上最后是在后面复制了 redrum，也就是说我们找到一个最右端为 \(n\) 的最长回文串，\(n\) 减去这个串的长度即为最优方案。
考虑如何计算。
求最大回文想到 manacher 算法，发现求出 \(p\) 数组后，若当前的右端点为最后一个字符的位置就可以计算，也就是当 \(p_i + i - 1 =m\) 时，答案为 \(n - p_i + 1\)。
/*
* @Author: Aisaka_Taiga
* @Date: 2023-10-23 15:12:00
* @LastEditTime: 2023-10-23 16:08:55
* @LastEditors: Aisaka_Taiga
* @FilePath: \Desktop\P9606.cpp
* The heart is higher than the sky, and life is thinner than paper.
*/
#include <bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n, ans, p[N], m;
char s[N], ss[N];
signed main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> ss[i];
s[0] = '~', s[++ m] = '%';
for(int i = 1; i <= n; i ++)
{
s[++ m] = ss[i];
s[++ m] = '%';
}
int r = 0, mid = 0;
for(int i = 1; i <= m; i ++)
{
if(i <= r) p[i] = min(p[2 * mid - i], r - i + 1);
while(s[i + p[i]] == s[i - p[i]]) p[i] ++;
if(p[i] + i > r) r = p[i] + i - 1, mid = i;
}
ans = n - 1;
// for(int i = 1; i <= m; i ++) if(s[i] != '%') cout << (p[i] / 2) << " "; cout << endl;
for(int i = 1; i <= m; i ++)
if(p[i] + i - 1 == m)
ans = min(ans, n - p[i] + 1);
cout << ans << endl;
return 0;
}