给定一个字符串，在所有它的唯一子字符串的排序(字典)序列中，原始字符串的级别是多少？

Question

给定一个字符串，它的所有唯一子字符串的排序(按顺序排列)中的原始字符串的等级。示例- abc唯一排序的子字符串序列是- a，ab，abc，b，bc，c。所以它的秩是3，是否有比生成所有唯一子字符串更好的方法，并在排序后找到它的秩。我用stl来回答这个问题，结果超过了时间限制。

Answer 1

首先，构建给定字符串的后缀数组。

例如，如果字符串为"ABABA"，则其后缀数组sa[]和高度数组height[i]=LCP(sa[i],sa[i-1])将为：

| i    | sa[i] | height[i] |
| ---- | ----- | --------- |
| 1    | A     | 0         |
| 2    | ABA   | 1         |
| 3    | ABABA | 3         |
| 4    | BABA  | 0         |
| 5    | BA    | 2         |

您可以看到，在ABABA之前的每个子字符串都属于后缀数组中的后缀，而不是ABABA。例如：

• A，属于sa[1]。
• A、AB和ABA属于sa[2]。但是第一个子字符串是重复的。
• A，AB，ABA，ABAB，ABABA属于sa[3]。但是前三个子字符串是重复的。

因此，如果整个字符串在后缀数组中被排序为#n，答案将是：

\sum_{i=1}^{n} length(sa[i]) - height[i]

所以"ABABA“的答案是1+3+5-1-3=5。

您可以获得这个问题的全部源代码，这里。没有经过充分的测试，但应该是有效的。

Answer 2

为给定字符串构建后缀数组

为该后缀数组创建最长公共前缀数组

在后缀数组中原始字符串的位置之前计数唯一的子字符串