题解：P4324 [JSOI2016] 扭动的回文串

wuxigk · 2025-04-10 03:52:22 · 题解

现有题解好像都带个 \log，这里给个线性时间解法。前两种情况用Manacher算法可以直接做到线性，因此主要关注第三种情况。

可以注意到如下性质：存在某个最长扭动回文串，其 AB 分界线到回文中心的距离等于回文中心在原串中的最长回文半径。

证明是直观的：任意考虑一个最长扭动回文串，如果它已经满足这一性质，则结束，否则不妨设回文中心在 A 中。将分界线不断地向右移动，可以发现只要不移出最长回文半径的范围，得到的串就不会改变，因此可以一直把分界线移到最长回文半径处，得到一个最长且满足性质的扭动回文串。

上述性质说明可以通过扩展极长回文子串的方式得到答案，由此得到一个 O(n\log{n}) 的做法，即枚举每个回文中心，以最长回文半径为下界做二分，用字符串哈希判断是否回文。

为了消掉 \log，可以维护当前已知的最大长度，枚举回文中心时先对最大长度加一用字符串哈希 O(1) 时间判断一下，如果不回文说明不可能更优，如果回文就逐字符扩展，直到不回文，稍微分析一下就会发现这部分用时是线性的。

核心代码如下：

int solve(const string& a, const string& b) {
    int n = a.length();
    string aa("#"), raa("#"), rbb("#");
    for (int i = 0; i < n; i++) {
        aa += a[i];
        aa += '#';
        raa += a[n - i - 1];
        raa += '#';
        rbb += b[n - i - 1];
        rbb += '#';
    }
    n = 2 * n + 1;
    auto man = manacher(aa);
    str_hash hash(aa), hrash(raa), hrbsh(rbb);
    int mx = 1;
    for (int i = 1; i < n; i++) {
        mx = max(mx, man[i]);
        if (i + mx >= n)
            continue;
        auto lh = hash.substr_hash(i - mx, i);
        auto rhl = hrash.substr_hash(n - i - man[i] - 1, n - i - 1), rhr = hrbsh.substr_hash(n - i - mx + 1, n - i - man[i]);
        pair<int, int> rh{ (rhl.first + 1LL * rhr.first * hash.pow1[man[i] + 1] % mod1) % mod1,(rhl.second + 1LL * rhr.second * hash.pow2[man[i] + 1] % mod2) % mod2 };
        if (lh.first != rh.first || lh.second != rh.second)
            continue;
        int d = mx + 1;
        while (i - d >= 0 && n - i - d + 1 >= 0 && aa[i - d] == rbb[n - i - d + 1])
            d++;
        mx = max(mx, d - 1);
    }
    return mx;
}
int main() {
    read<int>();
    string a, b;
    cin >> a >> b;
    auto ra = a, rb = b;
    reverse(ra.begin(), ra.end());
    reverse(rb.begin(), rb.end());
    cout << max(solve(a, b), solve(rb, ra));
    return 0;
}