HDOJ 4333 Revolving Digits(KMP+扩展KMP)
超级传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4333
本题需要注意一点，需要统计的只是不重复的数字，所以先要用KMP求出串的循环节，然后只取一个周期进行匹配就行。用扩展KMP进行匹配，母串为输入串的两倍扩展(便于表示循环位移)，在匹配的过程中判断大小。
代码如下：
#include <cstdio>#include <cstring>using namespace std;typedef struct __ans{ int L, E, G;}Ans;char A[200020];char B[100010];int P[100010];void preprocess(char* B, int* P, int m = -1){ P[0] = -1; int j = -1; if (m == -1) m = strlen(B); for (int i = 1; i < m; i++) { while (j != -1 && B[j + 1] != B[i]) j = P[j]; if (B[j + 1] == B[i]) j++; P[i] = j; }}Ans ex_kmp(char* A, char* B, int* P, int n = -1, int m = -1){ Ans ret = {0, 1, 0}; int a = 0, p, L; if (n == -1) n = strlen(A); if (m == -1) m = strlen(B); P[0] = m; while (a < m - 1 && B[a] == A[a + 1]) a++; P[1] = a; a = 1; for (int k = 1; k < m; k++) { p = a + P[a] - 1; L = P[k - a]; if ((k - 1) + L >= p) { int j = (p - k + 1) > 0 ? (p - k + 1) : 0; while (k + j < n && A[k + j] == B[j]) j++; P[k] = j; a = k; } else P[k] = L; if (P[k] == m) ret.E++; else if (P[k] < m) { if (A[k + P[k]] < B[P[k]]) ret.L++; if (A[k + P[k]] > B[P[k]]) ret.G++; } } return ret;}int main(){ int t; scanf("%d", &t); for (int i = 1; i <= t; i++) { scanf("%s", B); int m = strlen(B); preprocess(B, P, m); if (m % (m - P[m - 1] - 1) == 0) m = m - P[m - 1] - 1; memcpy(A, B, sizeof(char) * m); memcpy(A + m, B, sizeof(char) * m); A[m << 1] = '\0'; Ans ans = ex_kmp(A, B, P, m << 1, m); printf("Case %d: %d %d %d\n", i, ans.L, ans.E, ans.G); } return 0;}