题目
蒜头君发现了一个很好玩的事情，他对一个数作旋转操作，把该数的最后的数字移动到最前面。比如，数 可以得到
，这样就可以得到很多个数。
现在，蒜头君的问题是这些数中，有多少个不同的数小于原数，多少个等于原数，多少个大于原数。
旋转中可能会出现前导零，两数比较的时候可以忽略前导零的影响。
输入格式
输入一个整数 )。
输出格式
答案在一行中输出三个整数，分别是小于 ，等于
，大于
的个数，中间以空格隔开。
解析：
第一步，如何方便、快速地得到旋转后的数字？
可以考虑读入整数 N 为一个字符串，然后在后面接上一个同样的字符串。加入原字符串的长度为 length，那么新字符串的长度就是 2 * length。我们只需要利用 substr() 函数，就可以取出所有旋转以后的字符串，如下所示：
string s;
int length = s.size();
s += s; //两个字符串 s 连接到一起
for(int i=0; i<length; i++){
string temp = s.substr(i, length); //每一个字符串都可以这样取出
}
第二步，数字转换成了字符串，如何比较大小？
要知道，两个相同长度的字符串比较大小之后的结果恰好和两个整数比较大小的结果相同！（你们想象一下字符的字典序，是不是这样？）
所以，我们可以直接比较原字符串与旋转后的字符串的大小。
但是，需要注意题目。蒜头君的问题是这些数中，有多少个不同的数小于原数，多少个等于原数，多少个大于原数。
为什么会提到不同，因为新得到的每一个字符串 temp 可能会出现相同的字符串。比如，对于 123123 这个数，我们期望得到的数字是 123123、231231、312312 这 3 个，而不是将 123123 变成 123123123123 之后枚举出来的 6 个。所以，我们需要判断，旋转后得到的数字会不会有相同的。
第三步，如何判断这个数字是否存在循环？
如上图，如果 n 正好是错位部分长度的整数倍，根据等效性，错位部分就是最小的一个循环节。所以，如果满足 n % (n - 1 - fail[n - 1]) == 0 的时候，就存在循环节，长度为 n - 1 - fail[n - 1] ，否则不存在循环节。
fail[] 数组的求法，我们在教程里，已经有详细讲述了。
这样一来，重复数字的问题也就自然而然地被解决了。前导零也不需要特别处理了。但是这么做的话，123123 可以被正常处理，123123123 也可以得到正确的结果，因为对于他们来说，循环节都是 123，只需要拼接一段循环节到最后就可以了。然而，12312312312 求出的循环节 123 可不能被简单地拼接到最后，因为对于这个数字来说，12312312312 才是需要被拼接的。所以我们需要判断一下，最后一个是不是真的完整的循环节。
参考答案代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int cnt[3], len;
string s, s1, s2;
void compare_st(int u){
s2 = s.substr(u, s1.size()); // 旋转后的字符串
if(s1 > s2){ // s1 是原来输入的字符串
cnt[0]++;
}else if(s1 < s2){
cnt[2]++;
}else{
cnt[1]++;
}
}
int fail[maxn], n;
void getFail(string s){
n = s.size();
fail[0]=-1;
for(int i=1;i<n;i++){
int k=fail[i-1];
while(k>=0 && s[k+1]!=s[i]){
k=fail[k];
}
if(s[k+1]==s[i]){
k++;
}
fail[i]=k;
}
}
int main(){
cin >> s;
getFail(s); // 根据输入的字符串，推导出对应的 fail 数组
string loop;
if( n % (n-1-fail[n-1]) == 0){ // 判断是否存在循环节，如果存在就截取出来添加到 s 后面，如果不存在，就直接把 s 接在 s 后面。
loop = s.substr(0, n-1-fail[n-1]);
}else{
loop = s;
}
s1 = s;
s = s + loop;
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < loop.size(); i++){
compare_st(i);
}
cout << cnt[0] << " " << cnt[1] << " " << cnt[2];
return 0;
}
