string - 给定一个字符串，原始字符串在其所有唯一子字符串的排序(字典顺序)序列中的排名是多少

Question

给定一个字符串，原始字符串在其所有唯一子字符串的排序(字典顺序)序列中的排名是多少。示例 - abc唯一排序的子串序列是 -a,ab,abc,b,b​​c,c 。所以它的排名将是3。有没有比生成所有唯一子字符串并在排序后找到它的排名更好的方法。我对这个问题使用了 set STL 并得到了 Time Limit Exceeded。

Answer 1

首先，建立一个suffix array给定的字符串。

例如字符串为“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]。但是前 3 个子串是重复的。

所以如果整个字符串在后缀数组中排名#n，答案将是:

\sum_{i=1}^{n} 长度(sa[i]) - 高度[i]

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

你可以得到这个问题的完整源代码here .未经过全面测试，但应该可以正常工作。