Please tell Cyy whether this circular string is symmetrical.
The input file consists of multiple test cases.
For each test case, there’s only a string in a line to represent the circular string. The string only consists of lowercase characters. ( 1 <= N <= 65536 )
It’s guaranteed that the sum of N is not larger than 1000000.
For each test case, output “Yes” in a line if the circular string is symmetrical, output “No” otherwise.
aaaaaa abcde ababab aaaaba aabbaa
Yes No No No Yes
一句话题意：循环字符串能否断开形成回文串
循环的东西，很明显要直接复制一遍
回文串，很明显manacher
如果原串长度len为奇数，则找到的回文数长度m必须>=len且m为奇数
如果原串长度len为偶数，则找到的回文数长度m必须>=len且m为偶数
一开始总是超时，一直以为是判断输入结束不对，后来才发现是用了string，每次都用string生成！#a#b..,很耗时！
1 #include<iostream> 2 #include<stdio.h> 3 #include<math.h> 4 #include<stdlib.h> 5 #include<string.h> 6 #include<algorithm> 7 using namespace std; 8 9 int p[300000]; 10 bool manacher(char* s,int len){ 11 int length=0; 12 int maxRight=1; 13 int mid=1; 14 int l=strlen(s); 15 for(int i=1;i<l;++i) 16 { 17 if(i<maxRight) 18 p[i]=min(p[2*mid-i],maxRight-i); 19 else p[i]=1; 20 21 while(s[i-p[i]]==s[i+p[i]]) p[i]++; 22 23 if(p[i]+i>maxRight) 24 { 25 maxRight=p[i]+i; 26 mid=i; 27 } 28 length=p[i]-1; 29 if(len%2==0) 30 { 31 if(!(length<len||length%2==1)) 32 return true; 33 } 34 if(len%2==1) 35 { 36 if(!(length<len||length%2==0)) 37 return true; 38 } 39 } 40 return false; 41 42 } 43 44 int main() 45 { 46 int len; 47 char s[300000]; 48 49 while(~scanf("%s",&s)) 50 { 51 len=strlen(s); 52 for(int i=len;i>=0;--i) 53 s[i+len]=s[i]; 54 // cout<<s<<endl; 55 for(int i=2*len;i>=0;--i) 56 { 57 s[2*i+2]=s[i]; 58 s[2*i+1]=‘#‘; 59 } 60 61 s[0]=‘!‘; 62 // cout<<s<<endl; 63 64 if(manacher(s,len)==true) 65 cout<<"Yes"<<endl; 66 else cout<<"No"<<endl; 67 } 68 69 }
原文：https://www.cnblogs.com/noip/p/9570168.html