Description
Cyy likes something symmetrical, and Han Move likes something circular. Han Move gave you a circular string whose length is N, i.e. the i-th character of the string is the neighbor of the ( (i-1) mod N )-th character and ( (i+1) mod N )-th character.
As Cyy likes something symmetrical, you want to find out whether this string can be symmetrical. There’s an operation for you to make the string symmetrical. This operation is called “disconnect”. You can use “disconnect” only once to break the link between any two neighbor characters, making the circular string into a linear string. If you can use “disconnect” to make this string into a palindrome, this string can be considered to be symmetrical.
Please tell Cyy whether this circular string is symmetrical.
Input
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.
Output
For each test case, output “Yes” in a line if the circular string is symmetrical, output “No” otherwise.
Sample Input
aaaaaa abcde ababab aaaaba aabbaa
Sample Output
Yes No No No Yes
Sentence string: can a string be broken to form palindrome string?
The thing that circulate, it is very obvious that should be copied directly.
Palindrome string, obviously manacher
If the original string length len is odd, then the palindrome length m must be > =len and M is odd.
If the original string length len is even, then the palindrome length m must be > =len and m are even numbers.
At first, it always timed out, always thought it was wrong to judge the end of the input, but later found that it was using string, each time with string generation! #a#b.., it takes a lot of time.
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 }