分析

我们需要加几个字符在末尾将其变为回文串。那么我们可以很容易考虑到，回文中心一定在这个字符串上。那么当一个回文中心确定时，这个串其实也就确定了。那么添加的长度为 。所以我们就应该寻找最大的可行的 。那么当一个字符可以为回文中心时当且仅当，回文中心加上回文半径覆盖了第 个字符的。那么求出每个点的回文半径就做完了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e7 + 100;
char ch[N],S[N];
int n,cnt,p[N],ans;
int main() {
    scanf("%d%s",&n,ch+1);
    S[0] = '~';S[cnt = 1] = '|';
    for(int i = 1;i <= n;i++) {
        S[++cnt] = ch[i];S[++cnt] = '|';
    }
    for(int i = 1,mid = 0,r = 0;i <= cnt;i++) {
        if(i <= r) p[i] = min(p[mid*2-i],r-i+1);
        while(S[i - p[i]] == S[i + p[i]]) ++p[i];
        if(p[i] + i > r) r = p[i] + i - 1,mid = i;
        if(i + p[i] - 1 == cnt) ans = max(ans,p[i]);
    }
    printf("%d\n",n - ans + 1);
    return 0;
}