問題タブ [suffix-array]

サフィックス配列からLCPを構築するためのこのコードがどのように機能するかを誰かが説明できますか? ランクisuffixArr[]のサフィックスの文字列内のインデックスの値を保持するような配列です。 suffixArr[i]

一般化された接尾辞ツリーを構築したいと考えています。この実装にはhttp://www.daimi.au.dk/~mailund/suffix_tree.htmlを使用しています。私のコードは次のとおりです。

x = 35 の値の場合、コードは正常に動作していますが、x = 36 以上の場合、次のエラーが発生します

例外はこのファイルからのものですhttps://github.com/Yacoby/suffix-tree-unicode/blob/master/suffix_tree.py

値 x < 36 では機能するが、他の値では機能しない理由がわかりません。ここで何が起こっているのかを理解するのを手伝ってください。

こんにちは、質問です。

1. s1 にプレフィックス AAA があるかどうかを確認し、結果をブール変数 b に割り当てます。

2. s1 にプレフィックス AAA があるかどうかを確認し、結果をブール変数 b に割り当てます。

これは私がこれまでに持っているものです

本当にこれにこだわって、頭が真っ白になりました。だから助けていただければ幸いです

序文: 私の質問は主にアルゴリズムに関する質問なので、接尾辞と LCP 配列に慣れていなくても、おそらく助けてくれるでしょう。

このホワイトペーパーでは、文字列パターン マッチングにサフィックスと LCP 配列を効率的に使用する方法について説明します。

SA と LCP の動作と、アルゴリズムの実行時間を (パターンの長さと文字列の長さ) から (Chris Eelmaa の回答 here と jogojapans answer here のおかげで) に改善O(P*log(N))するP方法NをO(P+log(N))理解しました。

LLcpとの使用法を説明する図 4 のアルゴリズムを試してみましたRLcp。しかし、それがどのように機能するかを理解するのに問題があります。

アルゴリズム（ソースから取得）：

使用される変数名の説明:

ここで、次の例を使用してアルゴリズムを試してみたいと思います (一部はここから取得)。

たとえば、文字列を一致させようとbanすると、アルゴリズムが 0 を として返すことが期待されL_Wます。

アルゴリズムをステップ実行する方法は次のとおりです。

何かが欠けているような気がしますが、何がわかりません。また、 を呼び出す代わりに、事前計算された LCP 配列をどのように使用できるか疑問に思っていますlcp(v,w)。

で演習を行っていますCheckIOが、なぜこれが機能しないのか疑問に思っています。文字列のセットが与えられた場合、文字列のいずれかがセット内の他の文字列のサフィックスである場合、True を返そうとしています。それ以外の場合は偽。itertools を使用して、最初にタプルで必要な順列を生成しています。次に、各タプル (各 i) について、2 番目のタプルが最初のタプル (オプション 1) の最後にある場合の難しい方法を確認したかったのです。他の方法では .endwith 関数 (オプション 2) を使用していましたが、どちらもうまくいきません。これら 2 つのオプションに欠陥があるのはなぜですか?

例:

私はこれが答えとして機能することを知っています。しかし、なぜ私の元の方法がうまくいかないのか疑問に思っています。

今日、scala を使用してサフィックス配列を作成しようとしています。膨大な数のコードでできたのですが、圧縮とソートを使えば数行で作れると聞きました。

私が現在抱えている問題は、始まりにあります。二分探索とzipWithIndexを使って以下の「ツリー」を作成してみましたが、今のところ何も作成できていません。線だけでできるかどうかもわかりませんが、きっとあるはずです（笑）。

私がやりたいのは、「チーズケーキ」という単語からSeqを取得することです:

誰かが私を正しい道に導くことができますか?