软件
产品
题意： 求一个字符串中最长的回文子串长度是多少
题解：Manacher 模板 题
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
char str[maxn],new_str[2*maxn];
int p[2*maxn];
int Manacher(char* str,char* new_str,int* p){
// cout<<str<<endl;
// 初始化
int n=strlen(str),m=0;
new_str[m++]='$';
new_str[m++]='#';
for(int i=0;i<n;i++){
new_str[m++]=str[i];
new_str[m++]='#';
}
new_str[m]='\0';
// cout<<new_str<<endl;
// 计算p数组
int mx=0,id=1,ans = 0;
for(int i=1;i<m;i++){
p[i] = id<mx ? min(p[2*id-i],mx-i) : 1;
while(new_str[i+p[i]]==new_str[i-p[i]]) p[i]++;
if(i+p[i]>mx) mx=i+p[i], id=i, ans=max(ans,p[i]);
}
// for(int i=1;i<strlen(new_str);i++)printf("%d ",p[i]);cout<<endl;
printf("%d\n",ans-1);
return ans-1;
}
int main(){
while(~scanf("%s",str))
Manacher(str,new_str,p);
}
地址： ⭐⭐
题意：两长度相等的字符串A和B，求 A[l1…r1]+B[l2… r2 ] 满足r1=l2 能得到的最长回文串的长度
题解：先对A和B用Manacher求出对应的p数组及各自最长回文子串ma,mb，再枚举回文中心求到能拼接得到的最长回文子串mab，取(ma,mb,mab)的最大值
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
char strA[maxn],new_strA[2*maxn];
char strB[maxn],new_strB[2*maxn];
int pA[2*maxn],pB[2*maxn],n;
int Manacher(char* str,char* new_str,int* p){
// cout<<str<<endl;
// 初始化
int n=strlen(str),m=0;
new_str[m++]='$';
new_str[m++]='#';
for(int i=0;i<n;i++){
new_str[m++]=str[i];
new_str[m++]='#';
}
new_str[m]='\0';
// cout<<new_str<<endl;
// 计算p数组
int mx=0,id=1,ans = 0;
for(int i=1;i<m;i++){
p[i] = id<mx ? min(p[2*id-i],mx-i) : 1;
while(new_str[i+p[i]]==new_str[i-p[i]]) p[i]++;
if(i+p[i]>mx) mx=i+p[i], id=i, ans=max(ans,p[i]);
}
// for(int i=1;i<strlen(new_str);i++)printf("%d ",p[i]);cout<<endl;
// printf("%d\n",ans-1);
return ans;
}
int main(){
cin>>n>>strA>>strB;
int ansA=Manacher(strA,new_strA,pA);
int ansB=Manacher(strB,new_strB,pB);
int ans = max(ansA,ansB);
for(int i=0;i<=n*2+1;i++){
int t=max(pA[i],pB[i-2]);//减二是关键
while(new_strA[i-t]==new_strB[i+t-2])t++;
ans=max(ans,t);
}
cout<<ans-1<<endl;
}
//用strlen会超时
地址：⭐⭐⭐
题意：一个数组围成一个环，可以通过一个操作修改数组得到新数组，操作：将长为n的数组分为k份（n%k=0），第i份中的所有元素的异或和作为新数组的第i个元素，求元素最多的对称环
题解：1.可以将数组复制一遍来模拟环；2.预处理前缀异或和，避免重复计算；3.暴力枚举n的因子求出新的环；4.利用Manacher判断新的环是否对称
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+5;
int p[2*maxn];
int str[maxn],new_str[2*maxn];
int a[2*maxn],pre[2*maxn],c[2*maxn];
int MLC(int* str,int* new_str,int* p,int n){
// 初始化
memset(new_str, 0 ,sizeof(new_str));
int m=0;
new_str[m++]=-2;
new_str[m++]=-1;
for(int i=0;i<n;i++){
new_str[m++]=str[i];
new_str[m++]=-1;
}
// 求p数组
int mx=0,id=1,ans = 0;
for(int i=1;i<m;i++){
p[i] = id<mx ? min(p[2*id-i],mx-i) : 1;
while(new_str[i+p[i]]==new_str[i-p[i]]) p[i]++;
if(i+p[i]>mx) mx=i+p[i], id=i, ans=max(ans,p[i]);
}
// printf("%d\n",ans-1);
return ans;
}
int main(){
int n,ans=1;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n+1;i<=n+n;i++) a[i]=a[i-n];//环拆成链 复制数组
// for(int i=1;i<=n*2;i++) printf("%d ",a[i]);printf("\n");
for(int i=1;i<=n+n;i++) pre[i]=pre[i-1]^a[i];//预处理 计算前缀和
// for(int i=1;i<=n*2;i++) printf("%d ",b[i]);printf("\n");
for(int k = 1;k<=sqrt(n)&&(n%k==0);k++)
{//枚举n的因子 把项链分为n/k或k份
int len=n/k,num=k;
for(int i=0;i<len;i++){
for(int j=0;j<num;j++) c[j]=pre[(j+1)*len+i]^pre[j*len+i];
for(int i=0;i<num;++i) c[i + num] = c[i];
if(MLC(c,new_str,p,num*2)>num) {ans=max(ans,num); break;}
}
len=k,num=n/k;
for(int i=0;i<len;i++){
for(int j=0;j<num;j++) c[j]=pre[(j+1)*len+i]^pre[j*len+i];
for(int i=0;i<num;++i) c[i + num] = c[i];
if(MLC(c,new_str,p,num*2)>num) {ans=max(ans,num); break;}
}
}
printf("%d\n",ans);
}
地址：⭐⭐⭐
题意：有4种将一个字符串变为回文串，1.删除字符串的第一个字母；2.删除字符串的最后一个字母；3.在字符串的头部添加任意一个字母；4.在字符串的尾部添加任意一个字母。
删除一个第 i 种英文字母需要的花费是 Ai，添加一个第 i 种英文字母的花费是 Bi。
求将字符串 S 变成回文串需要的最小花费是多少？
题解：先利用前缀和求出删除或添加str[0,k]或str[k,n]需要的花费，再利用Manacher求出str对应的p数组，最后枚举回文中心 i 留下最长回文半径，然后单边保留一些或不保留字符，然后砍掉多余部分，最后在另一侧补全，使得字符串成为回⽂串。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INFLL = 1e18;
const int maxn=1e6+5;
int p[2*maxn];
ll pre[maxn],suf[maxn];
ll suml[maxn],sumr[maxn];
char str[maxn],new_str[2*maxn];
int add[30],del[30];
int Manacher(char* str,char* new_str,int* p,int n){
// cout<<str<<endl;
// 初始化
int m=0;
// new_str[m++]='$';
new_str[m++]='#';
for(int i=0;i<n;i++){
new_str[m++]=str[i];
new_str[m++]='#';
}
new_str[m]='\0';
// cout<<new_str<<endl;
// 计算p数组
int mx=0,id=1,ans = 0;
for(int i=1;i<m;i++){
p[i] = id<mx ? min(p[2*id-i],mx-i) : 1;
while(new_str[i+p[i]]==new_str[i-p[i]]) p[i]++;
if(i+p[i]>mx) mx=i+p[i], id=i, ans=max(ans,p[i]);
}
// for(int i=1;i<strlen(new_str);i++)printf("%d ",p[i]);cout<<endl;
// printf("%d\n",ans-1);
return ans;
}
int main(){
scanf("%s",str+1);
int n = strlen(str+1);
Manacher(str+1,new_str,p,n);
int m = strlen(new_str);
for(int i=0;i<26;i++)cin>>del[i]>>add[i];
for(int i=1;i<=n;i++){
suml[i]=suml[i-1]+del[str[i]-'a'];
pre[i]=min(pre[i-1],suml[i-1])+add[str[i]-'a'];
pre[i]=min(pre[i],suml[i]);
}
for(int i=n;i>=1;i--){
sumr[i] = sumr[i+1]+del[str[i]-'a'];
suf[i] = min(suf[i+1],sumr[i+1])+add[str[i]-'a'];
suf[i] = min(suf[i],sumr[i]);
}
ll ans = INFLL;
for(int i=0;i<=m;i++){
p[i]--;
if(i%2==0){//new_str[i]为#
int x = p[i]/2;
int l = i/2-x+1;
int r = i/2+x;
ans=min(ans,suml[l-1]+suf[r+1]);
ans=min(ans,pre[l-1]+sumr[r+1]);
}
else{//new_str[i]为字母
int x = p[i]/2;
int l = i/2-x+1;
int r = i/2+x+1;
ans=min(ans,suml[l-1]+suf[r+1]);
ans=min(ans,pre[l-1]+sumr[r+1]);
}
}
printf("%lld\n",ans);
return 0;
}
地址：⭐⭐⭐
题意：在字符串S中找到一个子串T，使得T 可分为两部分X，Y（|X|,|Y|≥1）且X和Y都是回文串。
题解：利用Manacher维护S对应的p数组的同时，维护两个数组pre[]和suf[]，其中pre[i]表示i为开头的原串中最长回文子串的长度；suf[i]表示i为结尾的原串中最长回文子串的长度。要注意此时的pre和suf并不准确,举个例子在…abcba…中第一个a的pre会在算完c处的p值后更新为5，但第一个b的pre值并不会改变，实际上b的pre值应该为3，即pre[b]=pre[a]-2，所以在Manacher之后还要递推更新一边pre和suf，最后遍历求pre[i]+suf[i]的最大值即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
char str[maxn],new_str[2*maxn];
int p[2*maxn];
int pre[2*maxn];//i为开头的原串中最长回文子串的长度
int suf[2*maxn];//i为结尾的原串中最长回文子串的长度
int Manacher(char* str,char* new_str,int* p){
// cout<<str<<endl;
// 初始化
int n=strlen(str),m=0;
new_str[m++]='$';
new_str[m++]='#';
for(int i=0;i<n;i++){
new_str[m++]=str[i];
new_str[m++]='#';
}
new_str[m]='\0';
// cout<<new_str<<endl;
// 计算p数组
int mx=0,id=1,ans = 0;
memset(pre,0,sizeof(pre));
memset(suf,0,sizeof(suf));
for(int i=1;i<m;i++){
p[i] = id<mx ? min(p[2*id-i],mx-i) : 1;
while(new_str[i+p[i]]==new_str[i-p[i]]) p[i]++;
if(i+p[i]>mx) mx=i+p[i], id=i, ans=max(ans,p[i]);
pre[i-p[i]+1]=max(pre[i-p[i]+1],p[i]-1);
suf[i+p[i]-1]=max(suf[i+p[i]-1],p[i]-1);
}
// for(int i=0;i<strlen(new_str);i++)printf("%d ",p[i]);cout<<endl;
// printf("%d\n",ans-1);
return ans-1;
}
int main(){
while(~scanf("%s",str)){
Manacher(str,new_str,p);
for(int i=1;i<=strlen(new_str)-1;i+=2) pre[i]=max(pre[i],pre[i-2]-2);
for(int i=strlen(new_str)-1;i>=1;i-=2) suf[i]=max(suf[i],suf[i+2]-2);
// for(int i=0;i<strlen(new_str);i++)printf("%d ",pre[i]);cout<<endl;
// for(int i=0;i<strlen(new_str);i++)printf("%d ",suf[i]);cout<<endl;
int ans = 0;
for(int i=1;i<strlen(new_str);i+=2) if(suf[i]&&pre[i]) ans = max(ans,suf[i]+pre[i]);
cout<<ans<<endl;
}
}
免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删
技术文档
热门文章
155-2731-8020
