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

最適な部分構造がないため、動的計画法を使用してこれを解決できるとは思いません。文字列の一部の答えを知っていても、その部分と別の文字については何もわかりません。

この問題は、文字列のすべてのサフィックスをトライに挿入してから、ノードの数を数えることで解決できます。これはO(n^2)、このような短い弦でACを取得する可能性が最も高いです。より効率的な方法には、接尾辞配列 ( O(n log n)) の使用と での接尾辞ツリーの構築が含まれO(n)ます。

于 2012-10-21T15:05:49.560 に答える