题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5442
题目大意：给你一个长度为n的字符串，将它首尾相连成环。问你这个环上找一个长度为n的字典序最大的串（你可以沿顺时针或逆时针找），如果有多个这样的串，输出首字母标号最小的，如果还有多个，输出顺时针的
解：
1、最小表示法解（时间复杂度：O(n)）
最小表示法~
2、后缀数组（时间复杂度：O(logn)）
比赛的时候想到的方法，然而并没有写出来，不好写+高时间复杂度=不推荐
最小表示法：
/*
* Problem:
* Author: SHJWUDP
* Created Time: 2015/9/16 星期三 16:18:36
* File Name: 1001.cpp
* State:
* Memo:
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> using namespace std; struct KMP {
int n;
string T; //target string
vector<int> nt;
KMP(const char * _str) {
n=strlen(_str);
T.assign(_str, _str+n);
getFail();
}
void getFail() {
nt.resize(n+);
nt[]=-;
for(int i=, j=-; i<n; ) {
if(j==- || T[i]==T[j]) {
nt[++i]=++j;
} else j=nt[j];
}
}
int match(const char * P) {//pattern string
//在P中找T
int ret=-;
for(int i=, j=; P[i]; ) {
if(j==- || P[i]==T[j]) {
++i;
if(++j==n) {
if(P[i]) ret=i-n;
}
} else j=nt[j];
}
return ret;
}
}; int maximum_representation(const char * s) {
int i, j, k, len=strlen(s);
for(i=, j=, k=; i<len && j<len && k<len; ) {
int tmp=s[(i+k)%len]-s[(j+k)%len];
if(tmp==) ++k;
else {
if(tmp>) j+=k+;//改成小于号是最小表示法
else i+=k+;
if(i==j) ++j;
k=;
}
}
return min(i, j);
} int n;
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
string str1;
cin>>str1;
int pos1=maximum_representation(str1.c_str());
string str2(str1.rbegin(), str1.rend());
int pos2=maximum_representation(str2.c_str());
str1+=str1;
str2+=str2;
KMP kmp(str2.substr(pos2, n).c_str());
pos2=kmp.match(str2.c_str());
auto cmp=[&]()->bool {
for(int i=; i<n; ++i) {
if(str1[pos1+i]!=str2[pos2+i])
return str1[pos1+i]>str2[pos2+i];
}
return pos1<=n-pos2-;
};
if(cmp()) {
printf("%d 0\n", pos1+);
} else {
printf("%d 1\n", n-pos2);
}
}
return ;
}
后缀数组：
/*
* Problem:
* Author: SHJWUDP
* Created Time: 2015/9/14 星期一 16:06:34
* File Name: 1001.cpp
* State:
* Memo:
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> using namespace std; struct SuffixArray {
static const int SIGMA_SIZE=;
int n;//串长+1
vector<int> str;//str中最后一个元素为0
vector<int> sa;//第i大后缀为str[sa[i]:]
vector<int> rank;//str坐标为i的后缀的字典序排名
vector<int> height;//sa[i-1]和sa[i]的最长公共前缀(LCP)
SuffixArray(const char * _str) {
n=strlen(_str)+;
str.resize(n);
for(int i=; i<n; ++i) str[i]=_str[i];
build_sa();
}
void build_sa(int m=SIGMA_SIZE) {
sa.assign(n, );
vector<int> x(n, ), y(n, ), c(m, );//c(字符计数)
//x[i]:str坐标为i的x值rank
//y[i]:y值第i大的str坐标
//*y数组中前k个为y段串不足k长度的串对应str坐标
for(int i=; i<n; ++i) ++c[x[i]=str[i]];
for(int i=; i<m; ++i) c[i]+=c[i-];
for(int i=n-; i>=; --i) sa[--c[x[i]]]=i;
for(int k=; k<=n; k<<=) {
int p=;
//直接利用sa数组排序第二关键字
for(int i=n-k; i<n; ++i) y[p++]=i;
for(int i=; i<n; ++i) if(sa[i]>=k) y[p++]=sa[i]-k;
//基数排序第一关键字
c.assign(m, );
for(int i=; i<n; ++i) ++c[x[y[i]]];
for(int i=; i<m; ++i) c[i]+=c[i-];
for(int i=n-; i>=; --i) sa[--c[x[y[i]]]]=y[i];
//根据sa和y数组计算新的x数组
swap(x, y);
p=; x[sa[]]=;
for(int i=; i<n; ++i) {
x[sa[i]]=y[sa[i-]]==y[sa[i]] && y[sa[i-]+k]==y[sa[i]+k]?p-:p++;
}
if(p >= n)break;
m = p;//下次基数排序的最大值
}
getHeight();
}
void getHeight() {
rank.resize(n);
height.resize(n);
for(int i=; i<n; ++i) rank[sa[i]]=i;
for(int i=, k=; i<n-; ++i) {
//h[i]=height[rank[i]]
if(k) --k; //h[i]>=h[i-1]-1
int j=sa[rank[i]-];
while(str[i+k]==str[j+k]) ++k;
height[rank[i]]=k;
}
}
}; int n;
bool cmp(string a, string b, int x, int y) {
for(int i=; i<n; ++i) {
if(a[x+i]!=b[y+i]) return a[x+i]>b[y+i];
}
return x<=n-y-;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
string str1;
cin>>str1;
string str2(str1.rbegin(), str1.rend());
str1+=str1;
str2+=str2;
SuffixArray sa1(str1.c_str());
int pos1;
for(int i=sa1.n-; i>=; --i) {
if(sa1.sa[i]<n) {
pos1=sa1.sa[i]; break;
}
}
SuffixArray sa2(str2.c_str());
int pos2=-, mi=n;
for(int i=sa2.n-; i>=; --i) {
if(pos2!=-) mi=min(mi, sa2.height[i+]);
if(mi<n) break;
if(sa2.sa[i]<n) pos2=sa2.sa[i];
}
if(cmp(str1, str2, pos1, pos2)) {
printf("%d 0\n", pos1+);
} else {
printf("%d 1\n", n-pos2);
}
}
return ;
}