連結：https://tioj.ck.tp.edu.tw/problems/1497

題目大意

給一個字串，求一個字串的Suffix Array。

題解

AC Code

使用 std::Sort

複雜度為 $O (| S | \log^{2} | S |)$

#include<bits/stdc++.h>
using namespace std;

vector<int> sa(string str)
{
    int len = str.size();
    vector<int> rank(len), sa(len), tmp(len);
    for(int i=0;i<len;++i)
    {
        rank[i] = str[i];
        sa[i] = i;
    }
    sort(sa.begin(), sa.end(), [&](int s, int e){
            return rank[s]<rank[e];
    });
    for(int i=1;i<=len;i*=2)
    {
        auto val = [&] (int s) { return make_pair( rank[s], s+i<len?rank[s+i]:-1 ); };
        sort(sa.begin(), sa.end(), [&](int s, int e){
            return val(s) < val(e);
        });
        tmp[sa[0]]=0;
        for(int j=1;j<len;++j) 
            if( val(sa[j]) == val(sa[j-1]) ) tmp[sa[j]] = tmp[sa[j-1]];
            else tmp[sa[j]] = tmp[sa[j-1]] + 1;
        rank.swap(tmp);
    }
    return sa;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string str;

    getline(cin, str);
    for(int i:sa(str)) cout<<i<<'\n';
}