3

私はこの質問の原因である問題の直接的な解決策を望んでいませんが、それはこの1つのリンクです：

したがって、文字列を取り込んで、内部で並べ替えられたセットとして実装されている接尾辞配列に追加します。次に取得するのは、指定された2つの文字列の辞書式順序のリストです。

S1 = "banana"
S2 = "panama"

SuffixArray.add S1, S2

最小の部分文字列の検索をk-th効率的にするために、このソートされたセットを前処理して、接尾辞とその前身の間にある最長の共通プレフィックスに関する情報を追加し、累積部分文字列の数を把握します。kしたがって、最後の項目の累積部分文字列数よりも大きい場合、それは無効なクエリであることがわかります。

これは、問題定義で指定された制約の小さな入力とランダムな大きな入力（長さ2000の最大50文字列）で非常にうまく機能します。7つのケースのうち4つを渡すことができ、かなり驚いていました。それらすべてを取得します。

それで私はボトルネックを探しに行きました、そしてそれは私を襲いました。これらのような入力の数が多い場合

anananananananana.....ananana
bkbkbkbkbkbkbkbkb.....bkbkbkb

k番目に小さい部分文字列のクエリは期待どおりに高速ですが、並べ替えられたセットを前処理する方法ではありません...セットの要素間の最長の共通プレフィックスを計算する方法は効率的ではなく、線形O（m）のようになります。これ、私はそれが十分に良いことを期待して最も素朴なことをしました：

m = anananan
n = anananana

Start at 0 and find the point where `m[i] != n[i]`

接尾辞とその前身は関係がない（つまり、異なる入力文字列からのものである）可能性があるため、このようになります。そのため、力ずくで仕方がないと思いました。

これがその時の質問であり、私が問題を減らすことになった場所です。上記の方法（複数の文字列で構成されている）のように、辞書式順序で並べ替えられた接尾辞のリストを指定します。

最長の共通プレフィックス配列を計算する効率的な方法は何ですか？。

その場合、サブ質問は、私のアプローチでは完全にマークから外れているのでしょうか？その場合は、さらに調査の手段を提案してください。

脚注、私は実装されたアルゴリズムを見せられたくありません、そして私はそう読むように言われることを気にしません、そしてそれでこれらの挑戦を試みている間私がとにかくそれがすることである主題に関する本またはリソース。

受け入れられた答えは、正しい道に私を導くもの、またはそれが失敗した場合になります。広い意味でこれらのタイプの問題を解決する方法を私に教えてくれる何か、本か何か

4

1 に答える 1

2

読む

スタンフォードからのこのチュートリアルPDFをお勧めします。

このチュートリアルでは、接尾辞配列と中間結果の行列を計算するためのO（nlogn）スペースを使用した単純なO（nlog ^ 2n）アルゴリズムについて説明します。中間結果のマトリックスを使用して、O（logn）の2つのサフィックス間の最長の共通プレフィックスを計算できます。

ヒント

自分でアルゴリズムを開発したい場合は、2^kの長いプレフィックスに基づいて文字列を並べ替えることが重要です。

チュートリアルから：

位置iから始まる長さ2^kのAのサブシーケンスをA（i、k）で表します。A（j、k）サブシーケンス（j = 1、n）のソートされた配列内のA（i、k）の位置は、P（k、i）に保持されます。

と

行列Pを使用して、最大のkから0までの降順を繰り返し、A（i、k）= A（j、k）かどうかを確認できます。2つのプレフィックスが等しい場合、長さ2^kの共通のプレフィックスが見つかりました。iとjを更新するだけで、両方を2 ^ k増やして、より一般的なプレフィックスがあるかどうかをもう一度確認します。

于 2013-01-11T20:02:15.170 に答える