题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3374
题意：给定一个串s，该串有strlen(s)个循环同构串，要求输出字典序最小的同构串的下标，字典序最小的出现次数，最大的同构串的下标，字典中最大的出现次数。
思路：对于求循环同构的字典序最小可以用最小表示法求得，最大也是一样。然后设ds为字符串s+s。然后就可以用KMP求最小串在ds出现的次数和最大串出现的次数了。
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
const int MAXN = + ;
typedef long long int LL;
#define INF 0x3f3f3f3f
int Representation(char *s,int l,bool flag){ //flag:0 最小表示法 flag:1 最大表示法
int i = , j = , k = ;
while (i < l&&j < l&&k < l){
int li, lj;
li = (i + k) >= l ? i + k - l : i + k;
lj = (j + k) >= l ? j + k - l : j + k;
if (s[li] == s[lj]){
k++;
}
else{
if (!flag){
if (s[li]>s[lj]){
i = i + k + ;
}
else{
j = j + k + ;
}
}
else{
if (s[li]<s[lj]){
i = i + k + ;
}
else{
j = j + k + ;
}
}
if (i == j){
j++;
}
k = ;
}
}
return i < j ? i : j;
}
int Next[MAXN];
void getnext(char *s,int lens){ //KMP的next数组
int j, k;
j = ; k = -; Next[] = -;
while (j < lens){
if (k == - || s[j] == s[k]){
Next[++j] = ++k;
}
else{
k = Next[k];
}
}
}
int KMP_Count(char *s,int lens,char *t,int lent){ //计算t串在s串中出现的次数
int ans = , j = ;
memset(Next, , sizeof(Next));
getnext(t,lent);
for (int i = ; i < lens; i++){
while (j> && s[i] != t[j]){
j = Next[j];
}
if (s[i] == t[j]){
j++;
}
if (j == lent){
ans++;
j = Next[j];
}
}
return ans;
}
char str[MAXN], dstr[MAXN*],minstr[MAXN],maxstr[MAXN];
//原串，原串*2后的串，字典序最小的串，字典序最大的串
int main()
{
while (~scanf("%s", str)){
int len = strlen(str);
for (int i = ; i < len * ; i++){
dstr[i] = str[(i%len)];
}
//计算最小
int minstart = Representation(str, len,);
for (int i = ; i < len; i++){
minstr[i] = str[(i + minstart) % len];
}
int mincount = KMP_Count(dstr, len * - , minstr, len);
//计算最大
int maxstart = Representation(str, len,);
for (int i = ; i < len; i++){
maxstr[i] = str[(i + maxstart) % len];
}
int maxcount = KMP_Count(dstr, len * - , maxstr, len);
printf("%d %d %d %d\n", minstart + ,mincount , maxstart + , maxcount);
}
return ;
}