点击查看代码
#include<bits/stdc++.h>using namespace std;const int N=8e5+10;
char str[N];
int ne[N];int main()
{int n;string s;cin>>n>>s;//构造反转拼接字符串for(int i=0;i<n;i++){str[n+2+i]=s[i];}str[n+1]='%';for(int i=1,j=2*n+1;i<=n;i++,j--){str[i]=str[j];}//构造ne数组for(int i=2,j=0;i<=2*n+1;i++){while(j&&str[j+1]!=str[i]) j=ne[j];if(str[j+1]==str[i]) j++;ne[i]=j;}cout<<n-ne[2*n+1]<<endl;return 0;}