Есть 1 миллион равных строк длины (короткая строка) .For напримерНайти перекрытие набора строк равной длины?
ABCDEFGHI
fghixyzyz
ghiabcabc
zyzdddxfg
. . .
Я хочу найти парное перекрытие двух string.The перекрытия А «ABCDEFGHI» и «B» fghixyzyz является «FGHI», который является максимальным суффиксом А, максимальный префиксом B, удовлетворяем суффикс и префикс равны.
Есть ли эффективный алгоритм, который может найти перекрытие любых двух строк в наборе?
Одним из эффективных способов является создание общего дерева суффиксов для набора строк. Чтобы найти перекрытие между строками x и y:
Следуйте за меткой пути для строки y в общем суффиксном дереве. Самый глубокий узел по этому пути, инцидентный терминальному символу строки x, имеет метку пути, которая эквивалентна перекрытию суффикса-префикса x-> y.
Подробнее см. На стр. 137 («Решение проблемы суффикса-префикса всех пар в линейном времени») книги Гусфилда «Алгоритмы для строк, деревьев и последовательностей».
Предупреждение: при использовании большого набора данных (миллионы/миллиарды строк) используется много памяти.
Итак, если вы перекрываете, вы имеете в виду, что суффикс одного равен префиксу другого? – sukunrt
Я думаю, что этот вопрос был бы полезен. http://stackoverflow.com/questions/1285434/efficient-algorithm-for-string-concatenation-with-overlap – sukunrt
Право. перекрытие fghixyzyz и zyzdddxfg - zyz – user1416452