Longest Common Subsequence の長さ in Elisp

Common Subsequence 解説 や、 最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー で紹介されている問題。動的計画法やメモ化で計算量が減らせる例として知られている、とのこと。

(defun lcs-length (l1 l2)
  (cond
   ((or (null l1) (null l2)) 0)
   ((eq (car l1) (car l2))
    (+ (lcs-length (cdr l1) (cdr l2)) 1))
   (t
    (max
     (lcs-length l1 (cdr l2))
     (lcs-length (cdr l1) l2)))))
=> lcs-length

(lcs-length '(a b c b d a b) '(b d c a b a))
=> 4