suffix-array - 如何在c中实现后缀数组

Question

但是使用 C++ 很容易实现，因为算法头文件中有内置Sort()函数。
我已经经历了形成数组的朴素方法和 O(nlogn) 方法。在这两种情况下，该sort()函数都用于对后缀进行排序。

C中有什么好的方法吗？

Answer 1

你是说你用谷歌搜索“sort c”却一无所获？当我这样做时，我会看到几个有用的链接。例如，看看这个问题及其答案：C library function to do sort。此外，关于后缀数组的维基百科文章很好地概述了构造后缀数组的方法：O(N) 构造后缀树的方法，然后是后缀数组，O(N^2 log N) 排序后缀的方法（排序需要 O (N log N)次比较，每次比较都是O(N)，所以总时间是O(N^2 log N))，其他高级方法。Wikipedia 文章还指出了 Java、C/C++ 等的一些实现。