Как найти все общие подстроки, которые 3 или более символов

Question

Есть ли эффективный алгоритм для поиска и выгрузки всех общих подстрок (длиной 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. (В примере могут быть некоторые отсутствующие выходные данные, потому что их так много...)

Answer 1

Вы можете найти все общие подстроки, используя структуру данных, называемую обобщенным суффиксным деревом

Libstree содержит пример кода для поиска самой длинной общей подстроки. Этот пример кода может быть изменен для получения всех общих подстрок.