По какому алгоритму находить наибольшую общую подпоследовательность двух дублирующихся слов?

Даны 2 слова, например, 00011 и 001. очевидно, что наибольшая общая подпоследовательность этих слов - 001.
А как, по какому алгоритму вычислить наибольшую общую последовательность этих повторяющихся слов? например, ( 00011 )^3 и ( 001 )^4, т.е.
000110001100011 и 001001001001 ?
  • Вопрос задан
  • 361 просмотр
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Вообще, вот алгоритм для произвольных слов: https://e-maxx.ru/algo/longest_increasing_subseq_log

Его, наверно, можно ускорить для работы с повторяющимеся строками через возведение матриц в степень, но будет муторно.

Какие у вас там ограничения: длины строк и количество повторений?
Ответ написан
Alexandroppolus
@Alexandroppolus
кодир
В идеале у нас два слова (0^а 1^b)^m и (0^с 1^d)^n, где a, b, m, c, d - любые

если у тебя слова только такого формата, то не надо ничего сложного придумывать, а просто разобрать отдельные случаи (когда те или иные значения a, b, c, d равны нулю, или какие-то из них равны между собой).
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы