题解 | 后缀子串排序

#include <chrono>
#include <iostream>
#include <string.h>
using namespace std;
int Partton(string B[],int low,int high) {
    string pivot=B[low];
    while (low<high) {
        while (low<high &&B[high]>=pivot)--high;
        B[low]=B[high];
        while (low<high && B[low]<=pivot)++low;
        B[high]=B[low];
    }
    B[low]=pivot;
    return low;
}
void QuickSort(string B[],int low,int high) {
    if (low<high) {
        int pivot=Partton(B,low,high);
        QuickSort(B,low,pivot-1);
        QuickSort(B,pivot+1,high);
    }
}
int main() {
    string s;
    cin >> s;
    int len = s.length();
    string ex[1000];
    for (int i=0;i<len;i++) {
        ex[i]=s.substr(i,len-i);//从下标为i开始，截取长度为len-i的片段
    }
    QuickSort(ex,0,len-1);

    for (int i=0;i<len;i++) {
        cout << ex[i] << endl;
    }

}

partition函数中使用B[high] >= pivot和B[low] <= pivot，这里的比较是字符串之间的字典序比较，不是字符比较。这意味着当字符串的第一个字符相同时，会自动继续比较后续字符。