1

2 つの文字列の間のすべての一般的な部分文字列 (長さが 3 以上) を検索してダンプする効率的なアルゴリズムはありますか?

入力例:

Length   : 0    5    10   15   20   25   30

String 1 : ABC-DEF-GHI-JKL-ABC-ABC-STU-MWX-Y
String 2 : ABC-JKL-MNO-ABC-DEF-PQR-DEF-ZWX-Y

出力例:

In string 1           2
---------------------------
ABC-DEF   0           12
ABC-DE    0           12
BC-DEF    1           13
:
-ABC-     15,19       11
-JKL-     11          3
-DEF-     3           15
-JKL      11          3
JKL-      12          4
-DEF      3           15,23
DEF-      4           16
WX-Y      29          29
ABC-      0,16,20     0,12
-ABC      15,19       11
DEF-      4           16,24
DEF       4           16,24
ABC       0,16,20     0,12
JKL       12          4
WX-       29          29
X-Y       30          30
-AB       15,19       11
BC-       1,17,21     1,13
-DE       3           15,23
EF-       5           17,25
-JK       11          3
KL-       13          5
:

例では、「-D」、「-M」も一般的な部分文字列ですが、長さが 2 しかないため必須ではありません。

4

1 に答える 1

0

一般化された接尾辞ツリーと呼ばれるデータ構造を使用して、すべての一般的な部分文字列を見つけることができます

Libstreeには、最長の共通部分文字列を見つけるためのサンプル コードが含まれています。このコード例を変更して、すべての共通部分文字列を取得できます。

于 2012-10-08T17:52:52.193 に答える