题目链接：牛客 最长回文
有两个长度均为n的字符串A和B。可以从A中选一个可以为空的子串A[l1…r1]，B中选一个可以为空的子串B[l2…r2]，满足r1=l2，然后把它们拼起来（A[l1…r1]+B[l2…r2]）。求用这样的方法能得到的最长回文串的长度。注意：求的不是本质不同的回文串个数哦！！！
第一行一个数n
第二行表示字符串A
第三行表示字符串B
输出一行一个数表示答案
分别对两个字符串进行manacher预处理，找到他们自身回文的p[]数组
我们需要注意的r1=l2，即子串A和子串B的下标是连续递增的，且子串A的最后一个字符会被子串B的第一个字符覆盖，故匹配时，B字符串需要-2，因为经过manacher预处理，中间多了个‘#’字符，且我们可以以此字符的下标为中心，两边对称的匹配字符串，找到最大的回文串长度。
我要评论#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
vector<int>p1,p2;
void manacher(string &t,vector<int>&p)
{
string s="$";
int len=t.size(),mx=0,id=0;
for(int i=0;i<len;i++)s+='#',s+=t[i];
s+='#';
len=s.size();
p.resize(len+1,0);
for(int i=1;i<len;i++){
p[i]=i<mx?min(mx-i,p[2*id-i]):1;
while(i-p[i]>=1&&i+p[i]<=len&&s[i-p[i]]==s[i+p[i]])p[i]++;
if(i+p[i]>mx)mx=p[i]+i,id=i;
}
t=s;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int n,ans=0,temp=0;cin>>n;
string s1,s2;cin>>s1>>s2;
manacher(s1,p1);
manacher(s2,p2);
for(int i=1;i<2*n+2;i++){
temp=max(p1[i],p2[i-2]);
while(s1[i-temp]==s2[i-2+temp])temp++;
ans=max(ans,temp);
}
cout<<ans-1;
}
本文地址：https://blog.csdn.net/hrd535523596/article/details/107532131
如对本文有疑问， 点击进行留言回复！！
网友评论