Вопрос к программистам

[yuriyag]

Как правильно называется (или, иными словами - что мне забивать в поисковик ) следующая задача: нужно найти общее подмножество (или подмножества) в двух произвольных строках символов. Например: абыверлаг - кудывермак, ититьеготак - майнготизтит.
Понятно что-то придумать самому можно, но возможно есть какие-то наработки которые позволяют

Comments

[a_p]

Этой задачей постоянно занимаются биоинформатики (ищут общие последовательности в длинных цепочках). Ключевые слова можно посмотреть вот тут, например: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1637039/.

Ещё, по-моему, может помочь внимательное изучение хорошей реализации grep :)

[yuriyag]

Спасибо, но grep мне кажется не совсем подходит. grep это поиск заданной последовательности, а у меня в задаче нет никакой заданной заранее последовательности, её нужно как раз найти, сравнивая две произвольные цепочки.
Попробую посмотреть статью (с первого взгляда выглядит страшновато :))))

[a_p]

мне кажется некоторой неизбежностью последовательный поиск подпоследовательностей одной цепочки в другой.
Кстати, а какова там длина алфавита? В смысле, в твоей задаче последовательности реально составлены из 26 букв?
Точнее, меня интересует вопрос отношения длины алфавита и длины входных последовательностей.

Вообще, можно просто вычитать одну из другой побуквенно с разными сдвигами и участки, соответствующие группам нолей в результате, и будут искомыми общими подпоследовательностями. Это квадратичный метод, но мне что-то непонятно, как быстрее (можно закольцевать длинную строку для некоторого уменьшения циклов сдвига).

[yuriyag]

Спасибо!
Смотри ещё какyю прелесть мне Тома насоветовала: Https://qastack.ru/codegolf/182134/greatest-common-substring