問題タブ [suffix-array]

複数の文字列間で最も長い共通部分文字列を見つけるプログラムに取り組んでいます。接尾辞配列または接尾辞ツリーのいずれかを使用するようにアプローチを下げました。どちらがより良いアプローチであるか (もしあれば) とその理由を知りたいです。また、サフィックス配列については、2 つの文字列のアルゴリズムをいくつか見ましたが、2 つ以上の文字列のアルゴリズムは見ませんでした。堅実な例をいただければ幸いです。アドバイスをありがとうございます。

注: この問題に具体的に対処する他の質問はありませんでしたが、存在する場合はその方向を教えてください!

ここで見つかったサフィックス配列に関する元の論文を読んでおり、最終的にはこれに基づいて自分で実装することを計画していますが、解釈方法がわからない擬似コードが1行あり、検索しても何も見つかりませんでしたそれが何を言っているのかを英語で説明できる人に感謝します。

L _w = min(k:W ≤<sub>p A _pos[k]または k=N)

ここで、k は整数、W は文字列、≤<sub>p は辞書式順序を使用して比較することを意味し、A _pos[k]は A の k^番目に小さいサフィックスの位置であり、N は A の長さです。ありがとうございます。

n 文字の文字列に接尾辞配列を作成するには、次のようにします。

1. 最初に n 個の接尾辞 O(n) を生成します
2. そして、それらを O(n log n) に並べ替えます

総時間計算量は、O(n) + O(nlogn) = O(nlogn) となります。

しかし、私はそれが O(n^2 log n) であり、その方法を理解できなかったことを読んでいます。誰か説明してくれませんか？

2 つの文字列aとbそれぞれがあります。の長さaは以上ですb。最長の共通部分文字列を見つける必要があります。複数の回答がある場合は、先に来る部分文字列を出力する必要がありますb(開始インデックスが最初に来るように)。

注: と の長さはa最大b10 ⁶です。

サフィックス配列を使用して最長の共通部分文字列を見つけようとしました（クイックソートを使用してサフィックスをソートします）。複数の答えがある場合、最長の共通部分文字列の長さに等しいすべての共通部分文字列をスタックにプッシュしようとしました。

知りたかったのですが、これを行うより速い方法はありますか？

接尾辞配列のLCP配列を計算する方法は? 最も効率的である必要はありません。O(n log n) または O(n) で十分です。可能であれば、比較的簡単にコーディングできるもの。

必要に応じて、動的プログラミングO(m * n)、接尾辞ツリーO(m + n)、接尾辞配列O(nlog^2 n)を使用して、最長共通部分文字列を計算していました。最近、 O(n)で実行されるSuffix Automatonを学びました。これは非常に印象的です。

最長共通部分文字列の長さを簡単に計算できるコードを書くことができます。例えば：

そして、これはコードです：

しかし今、長さではなく、最長の共通部分文字列自体を出力する必要があります。しかし、コードを変更することはできません:(このコードを変更して、最も長い共通部分文字列を出力するにはどうすればよいですか?

文字列 S が与えられたとします。

S1 を接頭辞として、S2 を接尾辞として含む、S の個別の部分文字列の数を見つける必要があります。

S、S1、および S2 の範囲は非常に大きく、つまり O(10^5) になる場合があります。

たとえば。

S が「abcdcd」、S1 が「ab」、S2 が「cd」であるとします。

"ababcdcd" の個別の部分文字列は、"a"、"b"、"c"、"d"、"ab"、"bc"、"cd"、"dc"、"abc"、"bcd"、" cdc」、「dcd」、「abcd」、「bcdc」、「cdcd」、「abcdc」、「bcdcd」、「abcdcd」。個別の部分文字列の総数は、Suffix Array を使用して簡単に見つけることができます。質問を解決するために同じアイデアを拡張しようとしています。

これらの部分文字列のうち、接頭辞として「ab」、接尾辞として「cd」を含む部分文字列は、「abcd」、「abcdcd」です。

したがって、答えは 2 です。

PS: Suffix Array を使用していると思いますが、その方法はわかりません。助けてください。

巨大なテキストに部分文字列 (入力として) を含む単語を見つけようとしています。テキストは次のようになります: *america*python*erica*escape*.. 例: 入力: "rica" => 出力: america,erica

接尾辞配列を使用します。

私の擬似コード（pythonlike）は次のとおりです。

これは機能しますが、遅すぎます。LCP 配列はアルゴリズムの実行時間を改善するはずですが、その方法がわかりません。アドバイスをいただけますか？

前もって感謝します！