题解：AT_abc398_f [ABC398F] ABCBA

Eysiking · 2025-03-23 08:14:03 · 题解

KMP 板子题

题意不能再简述了，要想让添加上后缀形成的的回文字符串最短，我们要充分利用原字符串自身形成的回文子串。具体来说就是找原字符串的一个最长回文后缀。

将原字符串 s 的反转串 s2 拼接到 s 之前，也就是对 s2+s 做 kmp，得到的 next 数组最后一个数就是匹配的最长回文后缀长度。

注意两个串拼接起来可能会发生重叠，比如 AA，变为 AAAA，得到的最长回文后缀长度应该是 2，但是 next 数组会得到 4，所以我们实际处理 s2+"\#"+s 串来解决这个问题。

找到最长回文后缀后，将未形成回文的前半部分反转拼接到原字符串末尾即可。

代码如下：

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    string s2 = s;
    std::reverse(s2.begin(), s2.end());
    string tmp = s2 + "#" + s;
    int siz = tmp.size(), cn = 0;
    std::vector<int> next(siz, 0);
    for (int i = 1; i < siz; ++i) {
        while (cn > 0 && tmp[i] != tmp[cn]) {
            cn = next[cn - 1];
        }
        if (tmp[i] == tmp[cn]) {
            cn++;
        }
        next[i] = cn;
    }
    int k = next.back();
    string ans = s.substr(0, n - k);
    reverse(ans.begin(), ans.end());
    cout << s + ans << "\n";
    return 0;
}