問題タブ [suffix-array]

Longest Common Prefix（LCP）を使用して、文字列内のパターンの出現回数を見つけることができることを読みました。

具体的には、テキストの接尾辞配列を作成して並べ替えるだけで、バイナリ検索を実行して範囲を見つけて出現回数を把握する代わりに、連続する各エントリのLCPを計算するだけです。接尾辞配列。

バイナリ検索を使用してパターンの出現数を見つけることは明らかですが、LCPがここで出現数を見つけるのにどのように役立つかを理解することはできません。

たとえば、この接尾辞配列の場合banana：

LCPは、「banana」や「na」などの部分文字列の出現回数を見つけるのにどのように役立ちますか。

LCPがここでどのように役立つかを理解するのに何か助けはありますか？

次の質問に対して、O（n ^ 2）よりも優れたアプローチを見つけるのに苦労しています。

たとえば、文字列が与えられますxyxxz。

次に、指定された文字列の各プレフィックスで一致する文字の総数を見つける必要があります。

ここで、文字列の可能なプレフィックスは次のとおりです。

これが出力になります。私は次のコードを実行しました：

しかし、それはO（n ^ 2）です。より良いアプローチが必要です：おそらくO（n）またはO（nlogn）。

前もって感謝します。

説明してください：

n 文字のテキストに対応するサフィックス配列があり、m 文字のパターンのテキスト内のすべての出現箇所を検索したいとします。接尾辞は順序付けられているため、最も簡単な解決策は、O(log n) 比較を使用してパターンの最初と最後の出現 (存在する場合) をバイナリ検索することです。

pattern の最初と最後の出現を決定した後、 pattern のすべての出現を取得する方法を知る必要があります。

複数の文字列の最長の共通部分文字列を計算するために、接尾辞リンク (ここでは紙) を持つ factor-oracle を使用できますか? ここで、部分文字列とは、元の文字列の任意の部分を意味します。たとえば、「abc」は「ffabcgg」の部分文字列ですが、「abg」はそうではありません。

s12 つの文字列との共通部分文字列の最大長を計算する方法を見つけましたs2。たとえば、「$」など、文字列に含まれていない文字を使用して 2 つの文字列を連結することによって機能します。s次に、 lengthの連結文字列の各プレフィックスについて、i >= |s1| + 2その LRS (最長繰り返しサフィックス) の長さlrs[i]とsp[i](その LRS の最初の出現位置の終了位置) を計算します。最後に、答えは

私は、この方法を使用する C++ プログラムを作成しました。このプログラムは、|s1|+|s2| <= 200000オラクル因子を使用すると、ラップトップで 200 ミリ秒以内に問題を解決できます。

どちらの問題も suffix-array と suffix-tree を使用して高効率で解決できることはわかっていますが、factor oracle を使用して解決する方法はあるのでしょうか。factor oracle は簡単に構築でき (C++ で 30 行、suffix-array は約 60 行、suffix-tree は 150 行必要)、suffix-array や suffix-tree よりも高速に実行されるため、これに興味があります。

この OnlineJudgeで最初の問題の方法をテストし、ここで2 番目の問題をテストできます。

2つの文字列の中で最も短い珍しい部分文字列を見つける必要があります。つまり、2つの文字列がある場合a、そのb最も短い部分文字列の長さを見つける必要があります。ab

接尾辞配列を使用してこの問題を解決するにはどうすればよいですか？

n * lg（n）以下の複雑さで解決する

文字列内で重複しない最長の繰り返し部分文字列を見つける必要があります。使用可能な文字列のサフィックス ツリーとサフィックス配列があります。

オーバーラップが許可されている場合、答えは自明です (サフィックス ツリーで最も深い親ノード)。

たとえば、String = "acaca" の場合

重複を許容する場合は「aca」、重複を許容しない場合は「ac」または「ca」となります。

アルゴリズムまたは高レベルのアイデアのみが必要です。

PS: 試してみましたが、ウェブ上で見つけられる明確な答えはありません。

長さ n (1 <= n <= 100000) の文字列を考えてみましょう。最小の辞書式回転を決定します。たとえば、文字列「alabala」の回転は次のとおりです。

この質問は Stack で既に質問されていますが、明確な解決策がないため、再度質問します。今まで、私は次の進歩を遂げました。
1. S を取り、reverse(S)..let P=S+reverse(S) で
連結 2. 上記の文字列 P のサフィックス配列を構築

ここで私の質問は、サフィックス配列の最初の文字列を選択すると、この文字列size> strlen(S)のサイズのプレフィックスがstrlen(S)指定された文字列 S の最小回転になるということです。

私の結論は正しいですか？

「真珠のプログラミング」：真珠の文字列、セクション15.3（テキストの生成）では、作成者が入力ドキュメントからランダムなテキストを生成する方法を紹介しています。ソースコードには、わからないことがいくつかあります。

著者は次のように説明しています。「入力を読み取った後、k個のヌル文字を追加します（比較関数が最後から実行されないようにします）。」この説明は、これらの2行にコメントした後でもうまく機能するため、私を本当に混乱させます。なぜこれが必要なのですか？

文字列/部分文字列の検索を高速化するために、大きな PDF ドキュメントからある種の「文字列カタログ」を作成する必要があります。

メカニズムは次のように動作するはずです。PDF スキャナーは PDF ドキュメントをスキャンして文字列を探し、カタログ内のコールバック メソッドを呼び出してその文字列にインデックスを付けます。

では、このようなカタログを作成するには、どのような手法を使用すればよいでしょうか? 聞いたことがあります: - サフィックス ツリー - 一般化されたサフィックス ツリー - サフィックス配列

私は主に一般化された接尾辞ツリーの傾向があります。私は正しいですか、それとも間違っていますか？「通常の」接尾辞ツリーは、単一の文字列のインデックス作成にのみ適していると思います。

しかし、サフィックス配列はどうでしょうか? 一般化されたサフィックス配列はありますか?

文字列からサフィックス ツリーを構築するための C/C++ のコードをたくさん見つけましたが、一般化されたサフィックス ツリーを構築するためのコードはありません!

本当に巨大な文字列セットで文字列/パターン マッチングを行うための効率的なデータ構造を探しています。トライ、サフィックスツリー、サフィックスアレイについて知りました。しかし、これまでのところ、C/C++ ですぐに使用できる実装を見つけることができませんでした (そして、自分で実装するのは難しく、エラーが発生しやすいようです)。しかし、Suffix-Arrays が本当に探しているものであるかどうかはまだわかりません... libdivsufsort と esaxx を試しましたが、ニーズに合わせてそれらを使用する方法を見つけることができませんでした:

ユーザー入力に一致するように、定義済みの文字列セットをワイルドカード (または正規表現) と共に使用したいと考えています。事前定義された文字列の膨大なリストを取得しました

"とは *？" 「XYZとは？」"いくら *？" ...

今、私は最も一致する文字列を見つけたいと思っています (もしあれば、それはまったく一致します)。つまり、ユーザー入力: >XYZ とは? 「WHAT IS XYZ?」を見つける必要があります。「WHAT IS *?」ではなく、「WHAT IS SOMETHING?」"WHAT IS *?" を見つける必要があります。(* は任意の文字数のワイルドカードであると仮定します)。

構造の構築は時間的に重要ではありません (また、構造はスペース効率が非常に高い必要はありません) が、検索に時間がかかりすぎないようにする必要があります。どうすれば簡単にできますか？フレームワーク/ライブラリまたはコード例は大歓迎です

ありがとう