Поиск количества общих подпоследовательностей заданной длины (Описание ниже)
Пусть есть два массива чисел (последовательности) размерности n и m (1 <= n, m <= 40). Также дано некое число k.
Необходимо найти количество общих подпоследовательностей в двух массивах длины k, где 1 < k <= min(n, m).
Интересует алгоритмически эффективный способ без переборов (возможно некая модификация алгоритма поиска наибольшей общей подпоследовательности), потому что нужно использовать на больших массивах. Спасибо.
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Делаете массив размером NxM, как для LCS, но каждая ячейка содержит не одно число, а массив, список, или словарь, в котором хранятся количества общих подпоследовательностей, заканчивающихся в i/j элементах, и имеющих длины от 1 до k.