双倍回文(Double Palindrome) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    string s;
    cin >> s;
    // d2[i]: number of pairs centered between i-1 and i
    vector<int> d2(n, 0);
    int l = 0, r = -1;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
            ++k;
            // Whenever r expands to i + k - 1, check if center j = i - k/2 is valid
            if (i + k - 1 > r && (k % 2 == 0)) {
                int half = k / 2;
                if (d2[i - half] >= half) {
                    ans = max(ans, k * 2);
                }
            }
        }
        d2[i] = k;
        if (i + k - 1 > r) {
            l = i - k;
            r = i + k - 1;
        }
    }
    cout << ans << "\n";
    return 0;
}