牛客14894 最长回文 manacher

题目链接

其中借鉴的图片和部分说明来自传送门
先用manacher把两个串都预处理一遍,求出Len数组，然后再遍历第一个字符串(第二个按道理来说也可以，但是没试过)因为要求l1 = r2 所以再遍历到第i点时,我们要把比较第二个字符串的第i - 2位置的回文串长度，选择最长的一个当作回文中点，然后以这个回文中点的串的起始长度就是它的回文长度，然后再从当前回文串的左侧去跟第二个字符串在当前回文串的右端的位置进行比较，如果相等，那么回文串长度加1

因为以 i 为中心 PA / PB 为半径的回文串中，它的最小回文长度就达到了 PA / PB - 1
所以只要从 PA / PB 两端拓展看还能找到多少可以相匹配的字符就可以了

至于为什么要把B串的匹配位置定为i - 2, 是为了让到最后匹配的时候让待匹配字符与到最开始回文串的最后一个字符对齐比如图中第三个样例，A的回文长度为1，那么B中开始匹配的起点就是移动到A串中'A'底下的C，这就是移动到B串第i - 2的位置进行匹配的原因，而且也满足了B串的起点是A串中的终点。

目前我是这样理解的，因为我看的大部分博客都说的很简洁，让我这种蒟蒻很困惑，如若有什么错误，欢迎指正。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000 + 5;

char s1[maxn],s2[maxn];
char temp1[maxn * 2 + 1],temp2[maxn * 2 + 1];
int l1[maxn * 2 + 1],l2[maxn * 2 + 1];
int n;

int init(int mark = 0)
{
    char *t = !mark ? temp1:temp2;
    char *s = !mark ? s1:s2;
    t[0] = '@';
    for(int i = 1; i <= 2 * n; i += 2){
        t[i] = '#';
        t[i + 1] = s[i / 2];
    }
    t[2 * n + 1] = '#';
    t[2 * n + 2] = '$';
    t[2 * n + 3] = 0;
    return 2 * n + 1;
}

int manacher(int mark = 0)
{
    char *t = !mark ? temp1:temp2;
    char *s = !mark ? s1:s2;
    int *L = !mark ? l1:l2;
    int mx = 0,po = 0, ans = 0;
    for(int i = 1; i <= 2 * n + 1; i++){
        if(mx > i) L[i] = min(mx - i,L[2 * po - i]);
        else L[i] = 1;
        while(t[i-L[i]] == t[i + L[i]]) L[i]++;
        if(i + L[i] > mx){
            po = i;
            mx = i + L[i];
        }
        ans = max(ans,L[i]); 
    }
    return ans - 1;
}

int main()
{
    scanf("%d",&n);
    scanf("%s%s",s1,s2);
    init(),init(1);
    manacher(),manacher(1);
    int ans = 0;
    for(int i = 2; i <= 2 * n + 1; i++){
        int temp = max(l1[i],l2[i - 2]);
        while(temp1[i - temp] == temp2[i - 2 + temp]) temp++;
        ans = max(ans,temp);
    }
    printf("%d\n",ans - 1);
    return 0;
}