HDU 3374 String Problem（最小表示法 + KMP）
/*题意：环状字符串，输出最小表示数和最大表示数，和出现的次数题解：最小表示法 + KMP利用最小表示法求出最小表示数和最大表示数然后利用KMP求出字符串的最小循环节*/#include <iostream>using namespace std;const int nMax = 1000010;char S[nMax];int next[nMax];int solve1(int len)//最小表示法{int i, j, k;for(i = 0, j = 1, k = 0;i < len && j < len && k < len;){int t = S[(i + k) % len] - S[(j + k) % len];if(t == 0)k ++;else{if(t > 0) i += k + 1;else if(t < 0) j += k + 1;k = 0;if(i == j)j ++;}}return min(i, j);}int solve2(int len)//最大表示法{int i, j, k;for(i = 0, j = 1, k = 0;i < len && j < len && k < len;){int t = S[(i + k) % len] - S[(j + k) % len];if(t == 0)k ++;else{if(t > 0) j += k + 1;//只需要这里做一些改动即可else if(t < 0) i += k + 1;k = 0;if(i == j)j ++;}}return min(i, j);}void getNext(int len)//KMP求出next[]{next[0] = -1;int i = 0;int j = -1;while(i < len){if(j == -1 || S[i] == S[j]){i ++;j ++;next[i] = j;}elsej = next[j];}}int main(){//freopen("e://data.txt", "r", stdin);while(scanf("%s", S) != EOF){int len = strlen(S);int pos1, pos2;pos1 = solve1(len);pos2 = solve2(len);getNext(len);int c = len - next[len - 1] - 1;//c即为最小循环元if(len % c == 0)c = len / c;else//如果不能够被整除，则赋值为1c = 1;printf("%d %d %d %d\n", pos1 + 1, c, pos2 + 1, c);}return 0;}