問題タブ [suffix-array]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - サフィックス配列アルゴリズム
かなりの量の読書の後、接尾辞配列と LCP 配列が何を表しているかを理解しました。
Suffix array : 配列の各サフィックスの _lexicographic ランクを表します。
LCP 配列: 2 つの連続する接尾辞の間で一致する最大長の接頭辞が、辞書式に並べ替えられた後に含まれます。
私は数日以来、サフィックス配列とLCPアルゴリズムがどのように機能するかを理解しようと懸命に努力してきました。
Codeforcesから取得したコードは次のとおりです。
このアルゴリズムがどのように機能するかを理解できません。私は鉛筆と紙を使って例に取り組み、関連する手順を書きましたが、少なくとも私にとっては複雑すぎるため、その間のリンクを失いました.
例を使用した説明に関するヘルプは、非常に高く評価されています。
c++ - 間にスペースを追加することによって意味のある単語を形成する単語が与えられた
スペースのない文字列の例「Iamastudent」が表示されます。特定の単語が辞書に存在するかどうかを検証する定義済みの辞書機能が提供されます。この関数を使用すると、文字列にスペースを挿入して、「私は学生です」と出力する必要があります。
それは私のインタビューの質問で、C ++で解決しすぎると言われました。私は動的プログラミングを使用して解決しましたが、彼は私が与えた解決策が以下の質問と同じであることに満足していませんでした
スペースのないフレーズが与えられた場合、スペースを追加して適切な文を作成します
彼はトライまたはサフィックス配列を使用してそれを行うように私に頼みましたが、私は解決策を理解できませんでした。
tree - ノードがテキスト文字列に出現する回数を保持するように一般化サフィックス ツリーを変更する
Ukkonen の論文の手順を変更して、単語がテキストに出現する回数の値を保持するにはどうすればよいですか。文字列の頻度も提供する実装はありますか?
私が望む変更は、文字列「hehe」のようなものです。すべての「h」、「e」、「he」の頻度カウントは、ツリー内で 2 にする必要があります。レスト ノードのデフォルト値は 1 です。
これまでで最高のようなライブラリと、このような以前の質問がいくつか見つかりました。
しかし、どれも私の問題に対する十分な解決策を説明していません。また、非常に大きな辞書ファイル (約 10 億語) を処理する必要があります。次に、アルゴリズムは非常に高速である必要があります。そして、私はスペースについて少し妥協する準備ができています.
pattern-matching - 接尾辞ツリーを使用して、個別のサブシーケンスの数を数えることはできますか?
サフィックス ツリーを使用して、(部分文字列ではなく) 個別の部分列の数を数えることはできますか?
定義: 文字列のサブシーケンスは、残りの文字の相対位置を乱すことなく文字の一部を削除することによって、元の文字列から形成される新しい文字列です。(つまり、「ACE」は「ABCDE」のサブシーケンスですが、「AEC」はそうではありません)。
では、String S = "rabbbit"、サブシーケンスのパターン P = "rabbit" が与えられた場合、サフィックス ツリーを使用して、S 内の P の異なるサブシーケンスの数を見つけることができますか?
手動検査から 3 を返す必要があります。
「ウサギ」の接尾辞ツリーを描画してこの問題を解決することで、誰かがこのトピックについて良い教育をしてくれると本当にありがたいです。
注 - この問題は DP などの他の手法で解決できますが、接尾辞ツリーを使用して解決できるかどうかに興味があります。ありがとう！
arrays - マンバー マイヤーズ アルゴリズムを使用したサフィックス配列
論文http://webglimpse.net/pubs/suffix.pdfで理論を調べてみました
しかし、彼らが言うとき、私はちょっと迷っています
Ai を最初のバケットの最初の接尾辞 (つまり、Pos[0] = i) とし、Ai-h を検討します (ih < 0 の場合、Ai を無視して Pos[1] の接尾辞を取る、など)。 . Ai は最小の h シンボル文字列から始まるため、Ai-h はその 2h バケットの最初にあるはずです。
私はこの声明を理解することができません。ih < 0 の場合、Ai-h を無視できるのはなぜですか。フェーズ 1 で ih > 0 の場合、const 時間で位置を決定するには
1 つのサンプル impl はhttp://belbesy.wordpress.com/2012/10/10/spoj-649-distinct-substrings-suffix-arrays-nlgn/です。
c - qsortによるサフィックスのソート
文字列のサフィックスを qsort() でソートしようとしていますが、ソートされたリストを取得できません。
私は何をすべきか ？
これが私がやったことです：
これは私のcompare()関数です:
問題は、ソートされていないリストを取得していることです。
algorithm - 接尾辞配列で DC3 を DC2 として使用できないのはなぜですか?
サフィックス配列を構築するためにDC3に関する論文を読んでいます。計算が速くなるように、DC3 を DC2 として適用できないのはなぜですか?