链接：https://ac.nowcoder.com/acm/contest/330/I
来源：牛客网
自从 Applese 学会了字符串之后，精通各种字符串算法，比如……判断一个字符串是不是回文串。
这样的题目未免让它觉得太无聊，于是它想到了一个新的问题。
如何判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后能不能构成一个回文串？
最近刷kuangbin的kmp&manacher 然后就直接上manacher了。(还是有点不熟。。)
思路：先跑manacher 得到 p数组
如果原串是回文串 肯定可以(当时以为偶数不可以。。。)
如果不是的话，说明中间位置 肯定有不匹配的，
然后就s[i] == s[len-i-1] 找到中间的子串
比如 abceeba 中的 cee
然后 判断是否 满足 子串的回文长度 == 自串长度-1
满足 就 Yes 否则 No
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 char s[100010],snew[200010]; 6 int p[200010]; 7 int manacher() { 8 int l=0; 9 snew[l++]=‘$‘; 10 snew[l++]=‘#‘; 11 for(int i=0;s[i];i++) { 12 snew[l++]=s[i]; 13 snew[l++]=‘#‘; 14 } 15 snew[l]=0; 16 int mx=0,id=0,maxx=0; 17 for(int i=0;i<l;i++) { 18 p[i]=i<mx?min(mx-i,p[2*id-i]):1; 19 while(snew[i+p[i]]==snew[i-p[i]]) p[i]++; 20 if(i+p[i]>mx) { 21 mx=i+p[i]; 22 id=i; 23 } 24 if(p[i]>maxx) 25 maxx=p[i]-1; 26 } 27 return maxx; 28 } 29 int main() { 30 scanf("%s",s); 31 int len=strlen(s); 32 int slen=manacher(); 33 if(len==slen) { 34 printf("Yes"); 35 } else { 36 int i=0,l,r,j,maxx=0; 37 while(s[i]==s[len-i-1]) i++; 38 l=i,r=len-i-1; 39 for(j=(l+1)*2;j<=2*(r+1);j++) { 40 maxx=max(maxx,p[j]-1); 41 } 42 if(maxx==r-l) printf("Yes"); 43 else printf("No"); 44 } 45 }