水题一道。 不难发现，一个字符串由对串旋转而来，其本身也是一个对串，所以直接判断给出的字符串是不是对串就好。 这里判断对串用到了KMP算法中的Next数组 （参考本人另一篇文章：http://blog.csdn.net/rcy_zhu/article/details/53105405） Next数组可以求出最大字符匹配数，所以只要截取给出字符串的一半求一遍Next数组就好。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> using namespace std; const int maxn=1000002; string s; int num[30]; int Next[maxn]; void makenext(string t) { int i=0; int j=-1; Next[0]=-1; int len=s.length(); while(i<len) { if(j==-1||s[i]==t[j]) { i++; j++; Next[i]=j; } else j=Next[j]; } } int main() { while(cin>>s) { memset(num,0, sizeof(num)); int len=s.length(); if(len%2==1) { puts("NO"); continue; } for(int i=0; i<len; i++) num[s[i]-'a']++; int flag=0; for(int i=0; i<26; i++) { if(num[i]!=0&&num[i]%2==1) { flag=1; break; } } if(flag==1) { puts("NO"); continue; } memset(Next,0,sizeof(Next)); string t=s.substr(0,len/2); //cout<<t<<endl; makenext(t); // for(int i=1;i<=len;i++) // printf("%d ",Next[i]); // cout<<endl; if(Next[len]==t.length()) puts("YES"); else puts("NO"); } }