流离之人追逐幻影

用户名：pwj666

访问量：60250

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13962
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：188

你可能喜欢

manacher求最长回文子串

　　作者: 流离之人追逐幻影　　　　发表时间：2019-10-20 17:33:00 浏览：250　|　评论：0　

原题链接：[最长回文](https://ac.nowcoder.com/acm/problem/14894 "最长回文")
```
Longest palindrome string
描述

There have two characters string A and B whose length is n. You can select a substring A[l1..r1] from A, which can be empty, and select a substring B[l2..r2] from B, which can be empty. They have to satisfy r1=l2, then put them together(A[l1..r1]+B[l2..r2]). Find the length of the longest palindrome string that can be obtained by this method. (attention: Asking is not the number of palindrome strings that are not essentially different)

输入
First line first number n

The second line represents the string A

The third line represents the string B

输出
Output a line and a number to indicate the answer

输入样例 1

5
ZQZFC
NSZXL
输出样例 1

3
输入样例 2

7
NSZQZFC
CFZQZSN
输出样例 2

8
```
预备知识：manacher算法（搞懂这个算法弄了好几个小时TT）
参考文章：
[如何找到字符串中的最长回文子串？](https://mp.weixin.qq.com/s?src=11×tamp=1571561862&ver=1923&signature=mSZyEkPcV4a2QSQL66CAqvy6dMQKziTwdZonzG4PYydxQUe5PUs32OYX7XT1D1rMMSPHYwA1Ap5UFanZjqBELGS4pUURASmW4KVkYYfLQQyYpcsBeIEV1edTic1bpkdA&new=1 "如何找到字符串中的最长回文子串？")

[干货｜Manacher(马拉车)算法详解](https://mp.weixin.qq.com/s?src=11×tamp=1571558242&ver=1923&signature=p622SI2ar2oHxvvoZwPfUxogwphUOty4OPavA3CPf7wNNcHn*2cLY8peL1*ybEW5x4LiGzMXSNuARAvs-pZlHBxouRKvlYexw*aOwcRpldSg*kR1VMxqYIJXWZUZfMSy&new=1 "干货｜Manacher(马拉车)算法详解")

题解：
```
1.先用manacher求出关键数组p1[]，p2[]的值，即求出每一个p1[i],p2[i]的最大回文半径。

2.遍历从1开始的回文中心，所以要先求出以该点为回文中心的最大回文半径即：temp=max(p1[i],p2[i-2])；然后将该点的回文半径加1，直到a[该半径的左端]!=b[该半径的右端]，然后用ans把较大的回文半径记录下来。遍历完成ans就是预处理后的a[]和b[]的最长回文半径，是未处理之前a[]和b[]的两倍，所以ans-1就是最终答案。

当然方法不止一种，用hash的话 时间复杂度会更优秀，不过代码处理起来太繁琐。
```
AC代码：
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+5;
int  p1[maxn],p2[maxn];
//manacher算法
void manacher(char *s,int len,int *p)
{
    p[0]=1;
    int mx=0,id=0;
    for(int i=1; i<len; i++)
    {
        if(mx>i)
            p[i]=min(p[id*2-i],mx-i);
        else
            p[i]=1;
        while(s[i+p[i]]==s[i-p[i]])
            p[i]++;
        if(i+p[i]>id+p[id])
        {
            id=i;
            mx=i+p[i];
        }
    }
}

char a[maxn],b[maxn];
int main()
{
    int n,N;
    cin>>n;
    cin>>a;
    cin>>b;
    N=n;
    //步骤1 
    //预处理 
    for(int i=n; i>=0; i--)
    {
        a[(i*2)+1]='#';
        a[(i*2)+2]=a[i];
        b[(i*2)+1]='#';
        b[(i*2)+2]=b[i];
    }
    a[0]='@';
    b[0]='@';
   
    manacher(a,n*2+2,p1);//求出p1[]
    manacher(b,n*2+2,p2);//求出p2[]
	
	//步骤2 
    int ans=1;
    n=n*2+2;
    for(int i=2;i<n;i++){
        int tmp=max(p1[i],p2[i-2]);//以i-1为回文中心的最大回文半径 
        while(a[i-tmp]==b[i+tmp-2])tmp++;//拓展回文半径 
        ans=max(ans,tmp);//记录最大的回文半径 
    }
    if(N==1&&a[2]==b[2])ans--;//特殊情况
    printf("%d\n",ans-1);
    return 0;
}
```

参考代码2：
```
#include <bits/stdc++.h>
using namespace std;
#ifdef osayes
#include "header.cpp"
#endif
char s1[212345], s2[212345];
int len1[212345], len2[212345];
void manacher(char s[], int n, int len[]) {
    len[0] = 1;
    int right_side = 0, center = 0;
    for (int i = 1; i < n; i++) {
        if (right_side <= i) {
            len[i] = 1;
            for (int j = i + 1; j < n && 2 * i - j >= 0 && s[2 * i - j] == s[j]; j++) {
                len[i] += 2;
            }
            right_side = i + len[i] / 2;
            center = i;
        } else {
            len[i] = min(len[2 * center - i], 2 * (right_side - i) + 1);
            if (len[2 * center - i] >= 2 * (right_side - i) + 1) {
                for (int j = right_side + 1; j < n && 2 * i - j >= 0 && s[2 * i - j] == s[j]; j++) {
                    len[i] += 2;
                }
                right_side = i + len[i] / 2;
                center = i;
            }
        }
    }
}
const unsigned int key = 19;
struct string_hash {
    unsigned long long h[212345], pow_key[212345];
    void init(char s[], int n) {
        h[0] = s[0];
        pow_key[0] = 1;
        for (int i = 1; i < n; i++) {
            h[i] = h[i - 1] * key + s[i];
            pow_key[i] = pow_key[i - 1] * key;
        }
    }
    unsigned long long get(int l, int r) {
        if (l == 0) {
            return h[r];
        }
        return h[r] - h[l - 1] * pow_key[r - l + 1];
    }
} h1, h2;
int solve(string A, string B, int n) {
    for (int i = 0; i < n; i++) {
        s1[i * 2] = A[i];
        s2[n * 2 - i * 2 - 2] = B[i];
    }
    n = n * 2 - 1;
    manacher(s1, n, len1);
    manacher(s2, n, len2);
    h1.init(s1, n);
    h2.init(s2, n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int left_side1 = i - len1[i] / 2;
        int right_side1 = i + len1[i] / 2;
        int left_side2 = n + 1 - right_side1;
        int lower = 0, upper = min(left_side1, left_side2);
        while (lower < upper) {
            int mid = (lower + upper + 1) / 2;
            if (h1.get(left_side1 - mid, left_side1 - 1) == h2.get(left_side2 - mid, left_side2 - 1)) {
                lower = mid;
            } else {
                upper = mid - 1;
            }
        }
        int total = lower * 2 + len1[i];
        if (i % 2 == 1) {
            ans = max(ans, (total + 1) / 4 * 2);
        } else {
            ans = max(ans, total / 4 * 2 + 1);
        }
    }
    return ans;
}
int main() {
    int n;
    string A, B;
    cin >> n >> A >> B;
    string C = B, D = A;
    reverse(C.begin(), C.end());
    reverse(D.begin(), D.end());
    cout << max(solve(A, B, n), solve(C, D, n)) << endl;
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C++代码）

manacher求最长回文子串

评论区

精彩推荐

字符逆序（C语言代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

点我有惊喜！你懂得！

C二级辅导-同因查找（C语言代码）

不知道哪里错了

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

C语言训练-字符串正反连接（C语言代码）

【绝对值排序】（C++代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C++代码）

manacher求最长回文子串

评论区

精彩推荐

字符逆序 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

点我有惊喜！你懂得！

C二级辅导-同因查找 （C语言代码）

不知道哪里错了

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

C语言训练-字符串正反连接 （C语言代码）

【绝对值排序】 （C++代码）

　　评论区

字符逆序（C语言代码）

C二级辅导-进制转换（C语言代码）

C二级辅导-同因查找（C语言代码）

C语言训练-字符串正反连接（C语言代码）

【绝对值排序】（C++代码）