2

我正在解决这个问题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方法？

4

1 回答 1

2

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

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

于 2012-10-21T15:05:49.560 回答