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

Question

[Екатерина Воропаева]

Даны 2 слова, например, 00011 и 001. очевидно, что наибольшая общая подпоследовательность этих слов - 001.
А как, по какому алгоритму вычислить наибольшую общую последовательность этих повторяющихся слов? например, ( 00011 )^3 и ( 001 )^4, т.е.
000110001100011 и 001001001001 ?

Comments

[Alexandroppolus]

На всякий уточню: требуется именно подпоследовательность, а не обязательно подстрока?
(например, для строки "abc" строка "ac" - только подпоследовательность, а "ab" - подпоследовательность и подстрока)

Answer 1

[Wataru]

Вообще, вот алгоритм для произвольных слов: https://e-maxx.ru/algo/longest_increasing_subseq_log

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

Какие у вас там ограничения: длины строк и количество повторений?

Comments

[Екатерина Воропаева]

Ограничений нет, в этом и проблема. В идеале у нас два слова (0^а 1^b)^m и (0^с 1^d)^n, где a, b, m, c, d - любые

[Wataru]

Екатерина Воропаева, Всмысле, ограничений нет? Если число a занимает терабайт, то вы никак не подсчитаете ничего. Откуда задача-то вылезла?

[Екатерина Воропаева]

Wataru, мне нужно придумать алгоритм, который будет считать в теории и для таких больших чисел. Мне нужно это понять со стороны теоретической математики, а не программирования. Задача появилась в ходе работы над курсовой

[Wataru]

Екатерина Воропаева, Даже с учетом, что у вас весьма специфичные строки, похоже чего-то принципиально быстрее обычного квадратичного (по суммарной длине строки) ДП тут нет.

Answer 2

[Alexandroppolus]

В идеале у нас два слова (0^а 1^b)^m и (0^с 1^d)^n, где a, b, m, c, d - любые

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

Comments

[Wataru]

Кажется, тут все посложнее. Общий случай, когда все не равно нулю и друг другу, вообще мне пока непонятен.

[Alexandroppolus]

Wataru, да, я понял в чем тут может быть трудность... Кейс, когда m < n, но a > c или b > d.
Например, (0011)^5 и (01)^10

тупой способ - "поштучно" сопоставляя 0011 и 01, выходит 01010101011, итого длина 11

а если по умному, то (01)^10 рассматриваем как 010 101 010 101 010 101 01, и если выкидывать из каждой тройки среднюю цифру, то получается 00110011001101, длиной 14.

Как это всё классифицировать, пока тоже не пойму. Но весьма похоже, тут будет какая-то периодическая конструкция (с длиной периода не более чем a+b+c+d), и справа ещё некий короткий "хвост".

Все прочие кейсы тривиальны.

[Екатерина Воропаева]

вот этот вот "хвост" мне и мешает предположить, что возможно придумать некий алгоритм, хвост ведь в разных примерах, похоже, будет разным.