HDU - 6294 SA-IS后缀数组（思维）（2018CCPC女生赛）_后缀自动机sa-is

SA-IS后缀数组

解题思路：贪心从前往后扫，可以直接记录答案。关键在于处理相等的情况。实际上，相等的情况可以从后往前推出。

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
char str[1000005];
char ans[1000005];
 
int main(){
 
    int T;
    scanf("%d",&T);
    for(int qqq=1;qqq<=T;qqq++){
        memset(ans,0,sizeof(ans));
        int N;
        scanf("%d",&N);
        scanf("%s",str);
 
        for(int i=0;i<N;i++){
 
            if(str[i]<str[i+1]){
                ans[i]='<';
            }
            else{
                if(str[i]>str[i+1]){
                    ans[i]='>';
                }
            }
        }
 
 
        char cur=ans[N-1];
        for(int i=N-2;i>=0;i--){
            if(ans[i]==0)
                ans[i]=cur;
            else{
                cur=ans[i];
            }
 
        }
        ans[N-1]='\0';
        printf("%s\n",ans);
 
    }
 
    return 0;
}