1

頻度に従ってソートされたすべての部分文字列の頻度を見つける文字列が与えられます(降順)。

例: ababa {"a", "b", "a", "b", "a", "ab", "ba", "ab", "ba", "aba", "bab", "aba "、"abab"、"baba"、"ababa"}.

出力：

3,2,2,2,2,1,1,1,1

説明

3 a 2 b 2 ba 2 aba 2 ab 1 abab 1 baba 1 ababa 1 bab

解決

1）明らかな解決策の1つは、すべての文字列をハッシュマップに保持し、その頻度をカウントすることですが、比較にはo（n ^ 3logn）O（n ^ 2 * n）{n ^ 2個の部分文字列* O（n）が必要ですof string *logn (マップは Red black tree として維持されているため)} 2) すべての部分文字列を三分探索木に挿入し、各部分文字列の頻度を取得し、頻度 O(n^3 logn) を並べ替えます。

O(n^2) または O(nlogn) ソリューションが存在するかどうか疑問に思っています。

このようなhttp://www.quora.com/Given-a-string-how-do-I-find-the-number-of-distinct-substrings-of-the-string

4

1 に答える 1

1

O(n^2) ソリューションは、次の方法で実現できます。

  1. すべての部分文字列をトライに挿入します。これは O(n^2) で実行できます。

  2. すべての頻度を取得して並べ替えます。部分文字列の頻度は [0, n] の範囲内に限られることに注意してください。最悪の場合、n^2 個の数値が存在するため、バケット ソートではすべての数値が O(n^2) でソートされる可能性があります。

于 2015-06-09T19:38:06.290 に答える