题解：AT_abc398_f [ABC398F] ABCBA

endswitch · 2025-03-23 11:44:59 · 题解

难度严格小于 D 和 E。

题目本质上是将反串拼到原串后，有多少重合的部分。

做法有很多，这里讲一下 kmp 求 border 的做法。

将反串接在原串的前面，那么题目转化为求最长公共前后缀。

最后按题目格式输出即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 5;
int nxt[N << 1];
string s, t;

signed main() {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> s;

    t = s;

    reverse(t.begin(), t.end());

    int n = s.size(), m = t.size();

    string S = t + "?" + s;

    for(int i = 1, j = 0 ; i < (int)(S.size()) ; ++ i) {
        while(j && S[i] != S[j]) j = nxt[j - 1];

        if(S[i] == S[j]) {
            nxt[i] = ++ j;

            if(nxt[i] == m) j = nxt[j - 1]; 
        }
    }

    for(int i) 

    for(int i = 0 ; i < n ; ++ i)
        cout << s[i];
    for(int i = nxt[n + m] ; i < m ; ++ i)
        cout << t[i];

    return 0;
}