Длина самой длинной общей подпоследовательности двух строк

Question

Я пытаюсь написать функцию, которая вычисляет длину самой длинной общей подпоследовательности двух входных строк str1 и str2.

Это то, что у меня сейчас,

(define LCS
  (lambda (str1 str2)
    (if (OR (equal? str1 "") (equal? str2 ""))
        0
        (if (equal? (string-contains str1 (string-ref str2 0)) #t) 
            (+ 1 (LCS (substring str1 1 (string-length str1)) 
                      (substring str2 1 (string-length str2))))
            (LCS (substring str1 1 (string-length str1)) 
                 (substring str2 1 (string-length str2)))))))

Где string-contains возвращает true , если в строке есть определенный символ. Прямо сейчас кажется, что это работает, но я думаю, что может быть ошибка.

Answer 1

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

В данный момент ошибка в вашем коде заключается в том, что вы перемещаетесь по длине обеих строк одновременно с каждым рекурсивным вызовом. Например, произойдет сбой (я думаю, я не пробовал) со следующими двумя строками: (LCS "scheme" "emesch") Причина в том, что совпадающие подстроки не начинаются в одной и той же позиции в первой и второй строке.

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

Answer 2

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

Более полное объяснение и реализация в Схеме доступны в моем блоге .