洛谷P4555 最长双回文串

P4555 [国家集训队] 最长双回文串

思路

写这个题主要是为了练习manacher算法，当然也有很多其他的方法可以做。
注意到题目要求找的是两个回文串拼起来，而manacher算法刚好能计算出以每个位置为中心的最长回文子串。
这种左右两边拼接的问题考虑枚举分断点。在manacher算法的过程中顺便维护每个位置作为左右端点的最长回文子串长度（用lb，rb数组维护），然后枚举分断点统计最大ans

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 3e5, MAXN = maxn;
string getns(string s) {
    string ns = "$#";
    for (int i = 0; i < s.size(); i++) {
        ns += s[i];
        ns += '#';
    }
    ns += '^';
    return ns;
}
int d[maxn];
int rb[maxn], lb[maxn];
void manacher(string s) {
    int l = 0, r = 0, ans = 0;
    for (int i = 1; i < s.size(); i++) {
        if (i <= r) {
            d[i] = min(d[l + r - i], r - i + 1);
        } else {
            d[i] = 1;
        }
        while (s[i + d[i]] == s[i - d[i]]) {
            d[i]++;
            lb[i - d[i] + 1] = max(lb[i - d[i] + 1], d[i] - 1);
            rb[i + d[i] - 1] = max(rb[i + d[i] - 1], d[i] - 1);
        }
        d[i]--;
        if (i + d[i] > r) {
            l = i - d[i];
            r = i + d[i];
        }

        ans = max(ans, d[i]);
    }
}
signed main() {
#ifndef ONLINE_JUDGE
    freopen("../in.txt", "r", stdin);
#endif
    cin.tie(0)->ios::sync_with_stdio(0);
    string s;
    cin >> s;
    string ns = getns(s);
    manacher(ns);
    int ans = 0;
    // cout<<ns<<endl;
    FU(i, 0, ns.size()) {
        // cout<<lb[i]<<" "<<rb[i]<<endl;
        if (lb[i] != 0 && rb[i] != 0) // 注意不能是单边的情况
            ans = max(ans, lb[i] + rb[i]);
    }
    cout << ans << endl;
    return 0;
}