問題タブ [suffix-array]

接尾辞 arrayがあります。どのサフィックス配列が指定された配列と等しくなるか、文字列を取得する方法は?

例えば。この配列を考えてみましょう: [7, 6, 4, 2, 1, 5, 3]. 次に、文字列banana$は私にとって良いことですget_suffix_array(banana$) == [7, 6, 4, 2, 1, 5, 3]。

私はインターネット上で検索しました: k 反復部分文字列の多くのソリューションを、サフィックス ツリーを使用して見つけましたが、サフィックス配列を使用していませんでした。

与えられた文字列: abaababb

繰り返される部分文字列の最大数 ,k = 文字列の長さ = 6

最初は a[0..k]={0}

サブストリングの頻度: "a"= 4 したがって、a[4]=1;

部分文字列の頻度: "ab"= 3 したがって、a[3]=1;

サブストリングの頻度: "b"= 4 したがって、a[4]= a[4]+1 = 2; 等々..

複雑さ: < 配列生成の O(nlogn)。

接尾辞配列の使用:

「abaababb」の接尾辞:

Sort()ただし、アルゴリズム ヘッダー ファイルに組み込み関数があるため、C++ を使用して実装するのは簡単です。
配列を形成する単純な方法と O(nlogn) 方法の両方を経験しました。どちらの場合も、sort()関数はサフィックスのソートに使用されます。

Cで何か良い方法はありますか?

文字列のすべての部分文字列に対して、スペース効率の良いサフィックス トライを作成したいと考えています。文字列の長さが 5000 であると仮定すると、部分文字列の数は約 25*10^6 になり、ノードごとにサイズ 26 の linkd の配列が格納されるため、合計メモリ = 26*5000*5000 となり、実行時エラーが発生します。期待されています。スペース効率の良い接尾辞トライの解決策を手に入れました。ここでは、スペースの順序がほぼ線形になるように、選択の余地のないパスを圧縮します。しかし、私は理解できないので、誰かがこれから私を助けることができます.

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

例: 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

私はサフィックス配列について学んでおり、このチュートリアルから O(nlognlogn) 回でサフィックス配列を作成する方法を学びました。

今、私はO（nlogn）時間でサフィックス配列からLCP配列を作成する方法を考えています。明らかにO（n * n）アプローチを知っています。より良いものが欲しい

良いオンライン リソースが見つかりませんでした。助けてください。このトピックを完全に学ぶことができ、他の人にも役立ちます。

ありがとう

バナナ、アナナ、ナナ、アナ、ナ、アという文字列バナナの接尾辞のリストがあるとしましょう。各サフィックスをバケツに入れることができました。'a' で始まるサフィックスは 1 つのバケットに含まれ、'b' で始まるサフィックスは別のバケットに含まれます。n についても同様です。しかし、バケツ内の文字列を辞書順で効率的にソートすることはできませんでした。バケット a は、a、ana、anana のようになります。このため、Java でこの問題を効率的に解決することができません - http://www.spoj.com/problems/SARRAY/ 私は何日も立ち往生しています。コード/提案は大歓迎です。

私はアルゴリズムの複雑さに慣れていないため、次の 2 つのアルゴリズムの複雑さを理解できません。どちらも、指定された文字列のサフィックス配列を見つけます。最初のものは自分で作成したもので、2 つ目はインターネットで見つけたものです。どちらがより高速で、その理由を知りたいですか?

最初のアルゴリズム

2番目のアルゴリズム