字符串循环节，扩展KMP
题目意思：
给出一个 数字（数字的位数 最多 100000 位）。 每次把数字第i个放第一位， 然后按顺序数下去，
如果到最后一个，接着就数第 1 个。 n 位 的数字，可能有 n个不同的数字。
样例中的 “341”, 可能有 3 个排法： “341”， “413”。 “134”。
然后，题目问，一共有多少个 数字比原来的数字大，比原来的数字小，和原来的数字相等。
关键的是，这些数字要去重。
本题要点：
1、 开2 倍的空间，处理以每一位数字开头：
比如数字 “48691”（设为 s1）, 后面接上 “4869”, 就变成 “486914869”（设为 s2），
其中strlen(s1) = 5。 接着扫描 s2，下标从 0，扫描 到下标 4， 依次得到5 个数字，
“48691”, “86914”, “69148”, “91486”, “14869”. 这5 个数字，刚好是原来字符串 s1 ，以各个数字开头得到的。
2、对加长的字符串 s2， 进行扩展 KMP 算法运算。 得到 extend 数组。
extend[i] 的意义，表示s2 从第 i 位， 开始，连着 长度 extend[i] 的字符串， 等于 s2 的长度为 extend[i] 的前缀。
假设 len1 = strlen(s1), 如果 extend[i] >= len1, 说明，以第i位开始的字符串 和 原来的字符串相等。
如果 extend[i] < len1, 就比较 s2 的前缀的下标为 extend[i] 的字符 s2[Next[i]]， 和 当前 i 位置后的第 extend[i]
位的字符 s2[Next[i] + i] 的大小关系。从而判断 以第 i位 开始的字符串 与原来字符串的大小关系了。
3、原来字符串存在循环节的情况：
先对 s1 数组，运行 KMP 算法，求出 next 数组， 循环节 长度 cycle = len - next[len];
当然，只有 cycle 能整除时候，s1 才是由若干个完整的循环节 cycle 组成，此时的循环次数 step = len / cycle.
最后，算出来的那些 大于，小于，等于的 次数，全部要除以 step ，去重啊。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 200010;
char s1[MaxN], s2[MaxN], s3[MaxN];
int Next[MaxN], next1[MaxN];
int T;
int small = 0, deng = 0, big = 0;void kmp_next()
{
strcpy(s3 + 1, s1); int n = strlen(s1);next1[1] = 0;for(int i = 2, j = 0; i <= n; ++i){
while(j > 0 && s3[i] != s3[j + 1])j = next1[j];if(s3[i] == s3[j + 1])++j;next1[i] = j;}
}void getNext(char* str)
{
int i = 0, j, po, len = strlen(str);Next[0] = len;while(i + 1 < len && str[i] == str[i + 1])++i;Next[1] = i;po = 1;for(int i = 2; i < len; ++i){
if(Next[i - po] + i < Next[po] + po){
Next[i] = Next[i - po];}else{
j = Next[po] + po - i; if(j < 0)j = 0;while(i + j < len && str[j] == str[j + i])++j;Next[i] = j;po = i;}}
}void solve(int t)
{
strcpy(s2, s1); strcat(s2, s1);int len = strlen(s2); s2[len - 1] = '\0';getNext(s2);kmp_next();len = strlen(s1);int cycle = len - next1[len];int step = len % cycle == 0? len / cycle : 1; //一共有多少个循环节small = 0, deng = 0, big = 0;for(int i = 0; i < len; ++i){
if(Next[i] >= len){
++deng;}else{
if(s2[Next[i] + i] > s2[Next[i]]){
big++;}else{
small++;}}}printf("Case %d: %d %d %d\n", t, small / step, deng / step, big / step);
}int main()
{
scanf("%d", &T);for(int t = 1; t <= T; ++t){
scanf("%s", s1);solve(t);}return 0;
}/* 1 341 *//* Case 1: 1 1 1 */