牛客14894 最长回文 manacher马拉车

题目链接：牛客 最长回文

题目描述

有两个长度均为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