http://acm.hdu.edu.cn/showproblem.php?pid=5442
题意：
给出一串字符串，它是循环的，现在要选定一个起点，使得该字符串字典序最大（顺时针和逆时针均可），如果有多个字典序相同的，则输出下标最小的，如果下标也是相同的，则输出顺时针方向的。
思路：
用了三种方法：
①最简单的，暴力枚举所有情况，需要优化一下，先处理出字符串中字典序最大的单词，然后接下来的起点肯定是这个单词，否则就可以跳过这个起点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n,mx;
string s, best; int main()
{
// freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
cin>>s;
mx = -;
for(int i=;i<n;i++)
if(s[i]-'a' > mx) mx = s[i]-'a';
s += s; int pos, dir;
best = "";
for(int i=;i<n;i++)
{
if(s[i]-'a'!=mx) continue;
string tmp = s.substr(i,n);
if(tmp > best)
{
pos = i;
dir = ;
best = tmp;
}
}
reverse(s.begin(),s.end());
for(int i=n-;i>=;i--)
{
if(s[i]-'a'!=mx) continue;
string tmp = s.substr(i,n);
if(tmp > best)
{
pos = n--i;
dir = ;
best = tmp;
}
else if(tmp == best)
{
if(n--i<pos)
{
pos = n--i;
dir = ;
}
}
}
printf("%d %d\n",pos+,dir);
}
return ;
}
暴力枚举
②后缀数组：
正序复制一遍，求一遍后缀数组，那么sa数组中排名最后的肯定是字典序最大的，此时直接取该值即可。而且此时它一定是最小坐标。
但是求逆序的时候需要注意一下，此时就不能求最小坐标了，因为逆序了，所以最小坐标在原来的字符串中是最大的，所以此时就要求最大字典序情况下的最小坐标。那么此时就要利用height数组了，从底向上依次遍历sa数组，如果和上一个的公共前缀是>=n的话，此时字典序是相同的，但是上一个字符串的坐标更大。知道height值<n。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=+; int n;
char s[maxn];
char s1[maxn],s2[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn];
int Rank[maxn],height[maxn]; void build_sa(int m)
{
int *x=t,*y=t2;
//基数排序
for(int i=;i<m;i++) c[i]=;
for(int i=;i<n;i++) c[x[i]=s[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;
//基数排序第一关键字
for(int i=;i<m;i++) c[i]=;
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; //下次基数排序的最大值
}
} void getHeight(int n)
{
int i,j,k=;
for(i=;i<=n;i++) Rank[sa[i]]=i;
for(i=;i<n;i++)
{
if(k) k--;
int j=sa[Rank[i]-];
while(s[i+k]==s[j+k]) k++;
height[Rank[i]]=k;
}
} int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
scanf("%s",s);
for(int i=;i<n;i++) s[i+n] = s[i];
s[*n] = '';
int tmp = n;
n = *n+;
build_sa();
getHeight(n-);
n = tmp; int pos1;
memset(s1,,sizeof s1);
for(int i=*n;i>=;i--)
{
if(sa[i]<n)
{
pos1 = sa[i];
break;
}
}
strncpy(s1,s+pos1,n); reverse(s,s+*n);
tmp = n;
n = *n+;
build_sa();
getHeight(n-);
n = tmp; int pos2;
memset(s2,,sizeof s2);
for(int i=*n;i>=;i--)
{
if(sa[i]<n)
{
while(height[i]>n) i--;
pos2 = n--sa[i];
break;
}
}
strncpy(s2,s+n--pos2,n); if(strcmp(s1,s2)>) printf("%d 0\n",pos1+);
else if(strcmp(s1,s2)<) printf("%d 1\n",pos2+);
else
{
if(pos1<=pos2) printf("%d 0\n",pos1+);
else printf("%d 1\n",pos2+);
}
}
return ;
}
后缀数组
③最大表示法：
参考论文：https://wenku.baidu.com/view/c6c5e7335a8102d276a22fa6.html
算法的具体思路：
(1)开始时，将字符串复制两份，设置两个指针，i=0,j=1.
(2)k=0,然后反复迭代直到s[i+k]!=s[j+k]
(3)如果k=n,那么返回较小的值，否则看情况滑动指针
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = +; int n;
char s[maxn];
char s1[maxn],s2[maxn]; int solve1(char *x) //最大表示法坐标最小
{
int i = , j = , k = ;
while(i<n && j<n && k<n)
{
int t = x[i+k] - x[j+k];
if(!t) k++;
else
{
if(t>) j+=k+;
else i+=k+;
if(i==j) j++;
k=;
}
}
return i<j?i:j;
} int solve2(char *x) //最大表示法且坐标最大
{
int i = , j = , k;
while(i < n && j < n)
{
while(x[i+k] == x[j+k] && k < n) k++;
if (k == n) //这个意思就是以i开头的和以j开头的字符串相同
{
int len = abs(i - j); //len的长度就是循环节
return n - len + i; //取坐标最大的
}
else
{
int t = x[i+k] - x[j+k];
if(t>) j+=k+;
else i+=k+;
if(i==j) j++;
k = ;
}
}
if(j >= n) return i;
return j;
} int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
scanf("%s",s);
for(int i=;i<n;i++) s[i+n] = s[i];
s[*n] = '\0'; int pos1 = solve1(s);
memset(s1,,sizeof s1);
strncpy(s1,s+pos1,n); reverse(s,s+*n);
int pos2 = solve2(s);
memset(s2,,sizeof s2);
strncpy(s2,s+pos2,n); int t = strcmp(s1,s2);
if(t>) printf("%d 0\n",pos1+);
else if(t<) printf("%d 1\n",n-pos2);
else
{
if(pos1+<=n-pos2) printf("%d 0\n",pos1+);
else printf("%d 1\n",n-pos2);
}
}
return ;
}
最大表示法