string - 一連の等しい長さの文字列の重なりを見つけますか?

Question

等しい長さの文字列（短い文字列）は 100 万個あります。たとえば、

abcdefghi

フギクシズィズ

ギアブカブ

ジズダッドフグ

. . .

2 つの文字列のペアワイズ オーバーラップを見つけたい。同等。

セット内の任意の 2 つの文字列の重複を見つけることができる効率的なアルゴリズムはありますか?

Answer 1

効率的な方法の 1 つは、文字列セットの一般的なサフィックス ツリーを構築することです。文字列 x と y の間の重複を見つけるには:

一般的なサフィックス ツリーで、文字列 y のパス ラベルをたどります。文字列 x の終端記号に付随するこのパスに沿った最も深いノードには、接尾辞と接頭辞の重複 x->y に相当するパス ラベルがあります。

詳細については、Gusfield の著書「Algorithms on Strings, Trees, And Sequences」の 137 ページ (「Solving the all-pairs suffix-prefix problem in linear time」) を参照してください。

注意: データセットが大きい場合 (数百万/数十億の文字列)、これは大量のメモリを使用します。