Вопрос к программистам
Jan. 27th, 2022 02:17 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
yuriyagКак правильно называется (или, иными словами — что мне забивать в поисковик ) следующая задача: нужно найти общее подмножество (или подмножества) в двух произвольных строках символов. Например: абыверлаг — кудывермак, ититьеготак — майнготизтит.
Понятно что-то придумать самому можно, но возможно есть какие-то наработки которые позволяют оптимизировать производительность. Или это уже из области AI?
[Дисклаймер: сорри если спрашиваю что-то тривиальное, никогда подобными задачами раньше не занимался]
no subject
Date: 2022-01-27 02:36 pm (UTC)Ещё, по-моему, может помочь внимательное изучение хорошей реализации grep :)
no subject
Date: 2022-01-27 03:03 pm (UTC)Попробую посмотреть статью (с первого взгляда выглядит страшновато :))))
no subject
Date: 2022-01-27 03:32 pm (UTC)Кстати, а какова там длина алфавита? В смысле, в твоей задаче последовательности реально составлены из 26 букв?
Точнее, меня интересует вопрос отношения длины алфавита и длины входных последовательностей.
Вообще, можно просто вычитать одну из другой побуквенно с разными сдвигами и участки, соответствующие группам нолей в результате, и будут искомыми общими подпоследовательностями. Это квадратичный метод, но мне что-то непонятно, как быстрее (можно закольцевать длинную строку для некоторого уменьшения циклов сдвига).
no subject
Date: 2022-01-27 04:01 pm (UTC)Смотри ещё какyю прелесть мне Тома насоветовала: Https://qastack.ru/codegolf/182134/greatest-common-substring
no subject
Date: 2022-01-27 05:09 pm (UTC)no subject
Date: 2022-01-27 05:36 pm (UTC)no subject
Date: 2022-01-28 05:25 pm (UTC)no subject
Date: 2022-01-28 05:39 pm (UTC)no subject
Date: 2022-01-27 04:43 pm (UTC)от же ж люди, иттить
no subject
Date: 2022-01-27 05:11 pm (UTC)