Самая длинная общая подпоследовательность строк

Проблема:

Напишите функцию, которая принимает два массива строк в качестве входных данных и возвращает самую длинную непрерывную последовательность строк, которые встречаются в обоих.

Например, для следующих двух массивов:

a = [“/home”, “/register”, “/login”, “/user”, “/one”, “/two”]
b = [“/home”, “/red”, “/login”, “/user”, “/one”, “/pink”]

Вы должны вернуть следующее:

[“/login”, “/user”, “/one”]

Подход:

Ключевой вывод приходит из вопроса: «Существует ли рекурсивная подструктура проблемы, которую мы можем использовать?» и «Можем ли мы кэшировать промежуточные результаты рекурсивных вызовов?»

  1. Рассмотрим местоположения i и j в массивах a и b соответственно. Как найти самую длинную общую подпоследовательность массивов, начинающуюся сa[i] и b[j]?
  2. если a[i] == b[j], то длина оптимальной подпоследовательности равна единице плюс длина самой длинной общей подпоследовательности массивов, начиная сa[i+1] и b[j+1].
  3. В противном случае оптимальная подпоследовательность пуста.
  4. Мы можем использовать динамическое программирование для кэширования промежуточных вычислений рекурсивного вызова в хеш-таблице для последующего повторного использования.

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

Итеративная реализация с компактными циклами:

В чем сложность приведенной выше реализации? Мы вызываем функцию longest_recursive для каждой (i, j) пары индексов исходных массивов. Следовательно, сложность составляет не менее O(MN), где M и N — размеры двух массивов. Хотя мы делаем дальнейшие рекурсивные вызовы longest_recursive для каждого (i, j), обратите внимание, что все эти вызовы, кроме одного, возвращаются немедленно, используя постоянный поиск в таблице, и, следовательно, общая сложность составляет O(MN).

Этот анализ сложности подчеркивает ограничения рекурсивной реализации (хотя ее довольно хорошо иметь и легко программировать). Вот несколько других:

  1. Сигнатура функции longest_recursive длинная и представляет собой головную боль при обслуживании. Более короткая сигнатура функции всегда предпочтительнее.
  2. unordered_map не гарантирует поиск без коллизий, а в худшем случае поиск карты может выполняться не за постоянное время, что приводит к снижению производительности.
  3. Ошибки времени выполнения в рекурсии (особенно превышение глубины стека/плохие базовые случаи) трудно отлаживать.
  4. Для этой проблемы достаточно одной итерационной функции, чтобы вычислить max_count и обновить таблицу, что делает рекурсивную реализацию немного длиннее.

Мы можем изменить метод longest() выше и заменить рекурсивный вызов следующим образом:

Тестирование:

Эта задача демонстрирует использование метода ElementsAre тестов Gunit.

Несколько простых тестов для пустых списков:

Простые тесты для идентичных массивов и для массивов без общих элементов

И, наконец, сложный пример в условии задачи: