接尾辞アレイを使用して2つの文字列の最長の一般的なサブストリングを計算する

Question

$ o（n）$の複雑さで接尾辞アレイを構築する方法を学んだ後、接尾辞アレイのアプリケーションを発見することに興味があります。これらの1つは、$ O（n）$時間で、2つの文字列の間に最も長い一般的なサブストリングを見つけることです。インターネットで次のアルゴリズムを見つけました。

1. 2つの文字列を$ a $ aと$ b $を1つの文字列にマージします$ ab $
2. $ ab $の接尾辞配列を計算します
3. $ lcp $（最も長い一般的なプレフィックス）アレイを計算する
4. 答えは最大の値$ lcp [i] $です

私はそれを実装しようとしましたが、多くの実装の詳細が言われていませんでした（つまり、文字列を連結するとき、それらの間に特別な文字を置く必要があります（$ ACB $）？）、私のコードは多くのテストケースで失敗しました。誰かがこのアルゴリズムについてもっと詳しく説明できますか？

前もって感謝します。

ノート： 私はこのアルゴリズムの正しさを保証しません。ブログで見つけましたが、それが機能しているかどうかはわかりません。間違っていると思われる場合は、別のアルゴリズムを提案してください。

Answer 1

あなたのアルゴリズムはです 正しくない. 。接尾辞アレイと文字列のLCPアレイ、つまり効率的な実装を計算する方法を知っていると思います。コメントで指摘されているように、各コンポーネントが何であるか、なぜそれが機能するのかを理解してみてください。

まず、文字列の接尾辞アレイ（$ sa $）です。接尾辞アレイは、基本的には、昇順の辞書順に配置された文字列$ s $のすべての接尾辞です。より具体的には、値$ sa [i] $は、ポジション$ sa [i] $から始まる$ s $の接尾辞が、$ s $のすべての接尾辞の辞書版の順序で$ i $にランクされていることを示しています。

次は$ lcp $ arrayです。 $ lcp [i] $は最も長い一般の長さを示します プレフィックス 間に 接尾辞 $ sa [i-1] $および$ sa [i] $から始まります。つまり、辞書編集の順序で配置すると、2つの連続した$ s $の接尾辞の中で最も長い一般的な接頭辞の長さを追跡します。

例として、文字列$ s = abbabca $を考慮してください。辞書編集の接尾辞は$ {a、abbabca、abca、babca、bbabca、bca、ca } $になります。 -Indexed配列。 $ lcp $ arrayは$ lcp = [ - 、1、2、0、1、1、0] $です。

ここで、2つの文字列$ a $ a $と$ b $を与えられた場合、$ s = a ＃b $として連結します。ここで、$ ＃$は$ a $と$ b $の両方に存在しない文字です。このような文字を選択する理由は、2つの接尾辞（$ ab ＃dabd $と$ abd $など）のLCPを計算するときに、最初の文字列の終わりに比較が壊れます（1回しか発生しないため、2つしか発生しません。異なるサフィックスは同じ位置にそれを持つことはありません）、そしてしません "オーバーフロー" 他の文字列に。

これで、なぜ$ lcp $ arrayで連続した値を見る必要がある理由を確認できるはずです（引数は矛盾と$ sa $の接尾辞が辞書順にあるという事実に基づいています）。 $ lcp $ arrayを最大値のチェックし続けてください そのような 比較される2つのサフィックスは、同じ元の文字列に属していません。それらが同じ元の文字列に属していない場合（1つは$ a $、もう1つは$ b $で始まります）、最大の値は最大の共通サブストリングの長さです。

例として、$ a = abcabc $および$ b = bc $を考慮してください。次に、$ s = abcabc ＃bc $。ソートされた接尾辞は$ {ABC #BC、ABCABC #BC、BC、BC #BC、BCABC #BC、C、C #BC、CABC #BC } $です。
$ begin {align*} sa＆= [4、1、8、5、2、9、6、3、7] lcp＆= [ - 、3、0、2、2、1、1 、0] end {align*} $

これで、最大の値は$ lcp [2] = 3 $ですが、$ sa [1] $ $および$ sa [2] $の場合、どちらも文字列$ a $から始まります。だから、私たちはそれを無視します。一方、$ lcp [4] = 2 $は$ sa [3] $（サフィックス$ bc $ of $ b $に対応）および$ sa [4] $（サフィックス$ bcabc #bcに対応する$ a $）の$。したがって、これは2つの文字列の間の最も長い一般的なサブストリングです。実際のサブストリングを取得するには、長さ2ドル（最大の値）を取得します 実行可能 $ lcp $）サブストリング$ sa [3] $または$ sa [4] $から始まります。これは$ bc $です。

Answer 2

オンラインで見つけたアルゴリズムは完全に正しくありません。 Pareshが述べたように、それは彼から与えられた例で失敗します。

ただし、LCPのチェック中に確認する場合は、さまざまな文字列のサブストリングのLCPのみを確認してください。たとえば、文字列AとBのLCSを見つけている場合、LCPのチェック中に接尾辞アレイの隣接するエントリが同じ文字列からではないことを確認する必要があります。

詳細 ここ.

Answer 3

引用するアルゴリズムのようなものは、文字セットの一部ではない文字がセパレーターとして使用され、接尾辞/プレフィックス配列がに構築されている場合、実際に機能するはずだと思います。 除外します セパレーターを含むすべての文字列、おそらくデザイナーの意図。これは基本的に、2つの別々の文字列の接尾辞/プレフィックス配列を構築することに相当します。

アルゴリズムへのリンクを投稿した場合、将来のREFに役立ちます。ご了承ください ウィキペディア これのアルゴリズムが擬似コードと他の多くのアルゴリズムを持っています。また、オンラインで入手可能なほとんどの標準言語には実装があります。