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.

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

 #include<iostream>

 #include<stdio.h>

 #include<math.h>

 #include<stdlib.h>

 #include<string.h>

 #include<algorithm>

 using namespace std;

 int p[];

 bool manacher(char* s,int len){

     int length=;

     int maxRight=;

     int mid=;

     int l=strlen(s);

     for(int i=;i<l;++i)

     {

         if(i<maxRight)

         p[i]=min(p[*mid-i],maxRight-i);

         else p[i]=;

         while(s[i-p[i]]==s[i+p[i]]) p[i]++;

         if(p[i]+i>maxRight)

         {

             maxRight=p[i]+i;

             mid=i;

         }

         length=p[i]-;

         if(len%==)

         {

             if(!(length<len||length%==))

             return true;

         }

         if(len%==)

         {

             if(!(length<len||length%==))

             return true;

         }

     }

     return false;

 }

 int main()

 {

     int len;

     char s[];

     while(~scanf("%s",&s))

     {

         len=strlen(s);

         for(int i=len;i>=;--i)

         s[i+len]=s[i];

     //    cout<<s<<endl;

         for(int i=*len;i>=;--i)

         {

             s[*i+]=s[i];

             s[*i+]='#';

         }

         s[]='!';

     //    cout<<s<<endl;

         if(manacher(s,len)==true)

         cout<<"Yes"<<endl;

         else cout<<"No"<<endl;

     }

 }