poj1509+后缀数组+模板(最小表示)

给定一个字符串，字符串首尾衔接！问最小字典序是从哪位开始！！

后缀数组模板题

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<string>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int Maxn = 3e4+5;
int n, k,t;
string s;
int rank[Maxn], temp[Maxn],sa[Maxn];
bool (int i, int j){
    if(rank[i] != rank[j]) return rank[i] < rank[j];
    else {
        int ri = i+k<=n?rank[i+k]:-1;
        int rj = j+k<=n?rank[j+k]:-1;
        return ri < rj;
    }
}
void construct_sa(string s, int sa[]){
	n=s.length();
    for(int i=0; i<=n; i++) {
        sa[i] = i;
        rank[i] = i<n?s[i]:-1;
    }
    for(k=1; k<=n; k*=2){
        sort(sa, sa+n+1, compare_sa);
        temp[sa[0]] = 0;
        for(int i=1; i<=n; i++){
            temp[sa[i]] = temp[sa[i-1]] + (compare_sa(sa[i-1], sa[i])?1:0);
        }
        for(int i=0; i<=n; i++) rank[i] = temp[i];
    }
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		cin>>s;
		int len=s.length(),ans,dex=-1;
		s=s+s+char('z'+1);
		construct_sa(s,sa);
		for(int i=0;i<=2*len;i++)
			if(sa[i]<len)
			{
				printf("%dn",sa[i]+1);break;
			}
	}
	return 0;
}