题面
【题目描述】：
有一天，Silence对可以旋转的正整数十分感兴趣。在旋转操作中，他可以把后面的数字按照原位置不动地搬到剩下位置的前面。当然，他也可以完全不动这串数字。比如，他可以把123变为123，231,312三种。现在他想知道他能得到多少个不同的整数，但他又觉得这个问题太简单了，所以开始思考这所有的整数中有多少个比原数大，有多少个比原数小，又有多少个和原数相等。我们将保证原来的整数是正的，它没有前导0，但如果我们通过旋转得到一个带前导0的数字，我们忽略它的前导0,比如，104旋转后能变成041，我们将它看为41。
【输入描述】：
输入的第一行包含一个整数t(1<=t<=50)，这意味着测试数据的组数。
对于每组数据，只有一行包含一个整数n(n<=10^100000)，我们将确保n是一个没有前导0的正整数。【输出描述】：
对于每组数据，请输出一行包括三个整数，输出格式为"Case X: L E G"（不包含双引号）,X表示当前数据的组数。L表示通过旋转操作比n小的数字的个数。E表示通过旋转过后等于n的数字的个数。G表示通过旋转操作比n大的数字的个数。
【输入样例】：
1341
【输出样例】：
Case 1: 1 1 1
题解
首先, 注意到题目要求的整数是"不相同"的, 因此要把原数进行KMP去完整循环节.
然后跑一次扩展KMP, \(match[i]\)表示可以匹配的最大长度, 因此说明\(match[i] +1\)位是不匹配的, 比较这一位即可.#include#include #include const int L = (int)1e5; int main(){ #ifndef ONLINE_JUDGE freopen("revolving.in", "r", stdin); #endif int t; scanf("%d", &t); for(int cs = 1; cs <= t; ++ cs) { static char str[L <<1]; scanf("%s", str); int len = strlen(str); static int nxt[L]; nxt[0] = -1; int p = nxt[0]; for(int i = 1; i < len; ++ i) { for(; ~ p && str[p + 1] ^ str[i]; p = nxt[p]); nxt[i] = str[p + 1] == str[i] ? ++ p : p; } if(len % (len - nxt[len - 1] - 1) == 0) len -= nxt[len - 1] + 1; for(int i = 0; i < len; ++ i) str[i + len] = str[i]; static int mtch[L << 1]; mtch[0] = (len << 1) - 1; p = 1; mtch[p] = -1; for(; p + mtch[p] + 1 < len << 1 && str[mtch[p] + 1] == str[p + mtch[p] + 1]; ++ mtch[p]); int mx = p + mtch[p]; for(int i = 1; i < len << 1; ++ i) { mtch[i] = std::max(-1, std::min(mx - i, mtch[i - p])); for(; i + mtch[i] + 1 < len << 1 && str[mtch[i] + 1] == str[i + mtch[i] + 1]; ++ mtch[i]); if(i + mtch[i] > mx) p = i, mx = p + mtch[p]; } int L = 0, E = 1, G = 0; for(int i = 1; i < len; ++ i) if(mtch[i] + 1 >= len) ++ E; else if(str[i + mtch[i] + 1] > str[mtch[i] + 1]) ++ G; else ++ L; printf("Case %d: %d %d %d\n", cs, L, E, G); }}