問題タブ [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.
string - サフィックス配列でソートされているサフィックスの意味は何ですか?
サフィックス配列自体の定義は、文字列のすべてのサフィックスのソートされた配列であることを知っています。しかし、ここでこの並べ替え操作の重要性を理解しようとしていますか? 文字列のすべての接尾辞の配列を作成し、それを並べ替えずに LCP 配列の構築に進むとします。この状況で、最長回文部分文字列などの一般的な問題を解決しようとすると、何が失われるのでしょうか。最長の繰り返し部分文字列?
string - サフィックスオートマトンとは？
接尾辞オートマトンとは正確には何なのか、それがどのように機能し、接尾辞ツリーや接尾辞配列とどのように異なるのかを説明してもらえますか? すでにウェブで検索してみましたが、明確で包括的な説明に出くわすことができませんでした。
私が求めていたものに最も近い次のリンクを見つけましたが、それはロシア語であり、英語への翻訳は理解しにくかった.
arrays - 接尾辞配列をソートする方法は?
接尾辞配列と最長共通プレフィックスの例を見ていますが、接尾辞配列がどのようにソートされるかの基準がわかりません。彼らがバナナ $ を使用するウィキペディアの例を見ています。サフィックス配列がどのようにソートされるかを誰か説明してもらえますか? 私の最初の本能は長さでソートすることでしたが、ここでは明らかにそうではありません。
(これは彼らが使用した例ですhttp://en.wikipedia.org/wiki/Suffix_array )
これらのサフィックスは並べ替えることができます。
string - Suffix Array 線形時間を作成するための DC3/Skew アルゴリズムの実装について理解する
Karkkainen、P. Sanders による線形時間サフィックス配列作成アルゴリズムの実装を理解しようとしています。アルゴリズムの詳細については、こちらを参照してください。
全体的なコンセプトは理解できましたが、提供された実装と一致せず、明確に把握できませんでした。
これが私を混乱させている最初のコードパスです。
紙によると：n0、n1、n2は、i mod 3 =（0,1,2）で始まるトリプレットの数を表します
コードによると: n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3; => これらの初期化はどのように導出されたのですか?
論文によると: i mod 3 != 0 でトリプレットを連結した T` を作成する必要があります
コードによると：n02 = n0 + n2; s12 = [n02] ==> n02 はどうして？n12、つまり n1 + n2 である必要があります。
コードに従って: for (int i = 0, j = 0; i < n + (n0 - n1); i++) i%3 != 0; となるように s12 をトリプレットで埋めます。=> for ループが n + (n0 - n1) 回実行されるのはなぜですか? 単純に n1 + n2 にする必要があります。すべきではありませんか？
これらの理由により先に進むことができません :( 助けてください。
java - 接尾辞配列の実装エラー
接尾辞配列 by の実装でコンパイラ エラーが発生し続けArrays.sortます。
次のエラーが表示されます。
a は変数に解決できません
トークン ",", の構文エラー。予想される
トークン "-" の構文エラー -- 予想されるa
は変数
に解決できません b は変数に解決できません
次のコードでは: