c++ - 动态规划如何应用在这里？

Question

我正在处理这个问题 http://www.spoj.pl/problems/DISUBSTR/给定一个字符串，我们需要找到它的不同子字符串的总数。

Input

T- number of test cases. T<=20;
Each test case consists of one string, whose length is <= 1000

Output

For each test case output one number saying the number of distinct substrings.

Example

Sample Input:
2
CCCCC
ABABA

Sample Output:
5
9

    Explanation for the testcase with string ABABA: 
    len=1 : A,B
    len=2 : AB,BA
    len=3 : ABA,BAB
    len=4 : ABAB,BABA
    len=5 : ABABA
    Thus, total number of distinct substrings is 9.

我已经使用后缀数组的盲目实现解决了这个问题。但是，我想使用动态编程来解决它。但是我想不出任何方法来达到目的。时间复杂度也需要为 0(n*n) 或更快。请谁能指导我正确的方向.任何提示/建议/伪代码将不胜感激。我已经考虑了很长时间但想不出任何 DP 方法来解决问题？

Answer 1

我不认为你可以使用动态规划来解决这个问题，因为没有最佳子结构。知道字符串的一部分的答案并不能告诉您关于该部分的任何信息 + 例如另一个字符。

问题可以通过在trie中插入字符串的所有后缀来解决。然后计算它的节点数。这是 O(n^2) 并且很可能会使用如此短的字符串获得 AC。更有效的方法包括使用后缀数组 (O(n log n)) 并在 O(n) 中构建后缀树。