Найти перекрытие набора строк одинаковой длины?

Question

Есть 1 миллион строк одинаковой длины (короткая строка). Например

ABCDEFGHI

fghixyzyz

ghiabcabc

zyzdddxfg

,,,

Я хочу найти парное перекрытие двух строк. Перекрытие A "abcdefghi" и B "fghixyzyz" равно "fghi", что является максимальным суффиксом A, максимальный префикс B, удовлетворяют суффиксу, а префикс - равны.

Есть ли эффективный алгоритм, который может найти перекрытие любых двух строк в наборе?

Answer 1

Одним из эффективных способов является создание общего дерева суффиксов для набора строк. Чтобы найти перекрытие между строками x и y:

Следуйте метке пути для строки y в общем дереве суффиксов. Самый глубокий узел на этом пути, который является инцидентным терминальному символу строки x, имеет метку пути, которая эквивалентна перекрытию суффиксного префикса x->y.

Подробнее см. На стр. 137 ("Решение проблемы суффикс-префикс всех пар в линейном времени") книги Гусфилда "Алгоритмы на строках, деревьях и последовательностях".

Предостережение: при этом используется большой объем памяти, если ваш набор данных большой (миллионы / миллиарды строк).