题解 | #小易爱回文#

KMP求前缀和后缀

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int main()
{
    string s; cin >> s;
    string t(s.rbegin(), s.rend());
    int n = s.size();
    vector<int> ne(n * 2 + 2);
    s = ' ' + t + '*' + s;
    for (int i = 2, j = 0; i <= n * 2 + 1; i++)
    {
        while (j && s[i] != s[j + 1]) j = ne[j];
        if (s[i] == s[j + 1]) j++;
        ne[i] = j;
    }
    int len = ne[n * 2 + 1];
    string s1 = s.substr(1, len), s2 = s.substr(len + 1, n - len);
    string res = string(s2.rbegin(), s2.rend()) + s1 + s2;
    
    cout << res << endl;
    
    return 0;
}