Boring Non-Palindrome

题目链接：https://codeforces.com/gym/102307/problem/B

思路

因为只能从末尾加字符串，让其变成回文串，那么就可以找到以原字符串末尾结束的最长回文子串T(马拉车做)，然后把前面不属于T的部分命名成T2。然后输出原字符串，再反序输出T2。

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;
using namespace std;

string s;
int ans[maxn],str[maxn],lef[maxn];
int build(const string &s){
    int n = s.length(), m = (n + 1)*2, ret = 0;
    str[0] = '\n'; str[m] = '\t'; str[1] = '\r'; ans[1] = 1;
    for (int i = 1; i <= n; i++)
        str[i*2] = s[i - 1], str[i*2+1] = '\r';
    ans[1] = 1;
    for (int r = 0, p = 0, i = 2; i < m; ++i){
        if (r > i) ans[i] = min(r - i, ans[p * 2 - i]);
        else ans[i] = 1;
        while(str[i - ans[i]] == str[i + ans[i]]) ++ans[i];
        if (i + ans[i] > r) r = i + ans[i], p = i;
        ret = max(ret, ans[i] - 1);
    }
    for (int i = 2; i < m; i++) if (lef[i - ans[i] + 1] < i + 1) lef[i - ans[i] + 1] = i + 1;
    for (int i = 1; i <= m; i++) if (lef[i] < lef[i - 1]) lef[i] = lef[i - 1];
    return ret;
}
int left(int x){
    return lef[(x + 1) << 1] - ((x+1) << 1);
}

int main(){
    ios;
    cin>>s;
    int len = s.length();
    build(s);
    int lenr = 1;
    for(int i = 0;i<len;i++){
        int ll = left(i);
        if(i + ll - 1 == len-1) {
            lenr = ll;
            break;
        }
    }
    cout<<s;
    for(int i = len-lenr-1;i>=0;i--) cout<<s[i];
    return 0;
}