Schemeで最長共通部分列(Common Longest Subsequence)

# はじめに

こちらの記事

https://qiita.com/H20/items/1a066e242815961cd043#31%E6%A1%81dp

のScheme版を書いている。途中、最長共通部分列(Common Longest Subsequence)について調べていたところ長くなったので別記事にまとめてみた。

ダブリングについては元記事が参照している解説記事はあまり自分にはピンと来ず、ググった結果、下記のサイトが役に立った。感謝。

https://qiita.com/ophhdn/items/dce35806b2458d59e086

# アルゴリズムスニペット

## DP配列に直接部分列を詰め込んでいく方式

参考にしたサイトの例題を使い、出力は共通部分列をそのまま出すようにした。これだと処理の過程がわかりやすい。

```Scheme
(use gauche.array)

(let* [(X (string->vector "myabcuuu"))
       (Y (string->vector "abcjju"))
       (dp (make-array (shape 0 (+ (vector-length X) 1) 0 (+ (vector-length Y) 1)) '()))]

  ; CLSの処理
  (dotimes (i (vector-length X))
    (dotimes (j (vector-length Y))
      (cond [(eqv? (vector-ref X i) (vector-ref Y j))
             (array-set! dp (+ i 1) (+ j 1) (cons (vector-ref X i) (array-ref dp i j)))]
            [else (array-set! dp (+ i 1) (+ j 1)
                              (if (> (length (array-ref dp (+ i 1) j)) (length (array-ref dp i (+ j 1))))
                                (array-ref dp (+ i 1) j)
                                (array-ref dp i (+ j 1))))])))

  ; 出力
  (dotimes (i (+ (vector-length X) 1))
    (format #t "~%")
    (dotimes (j (+ (vector-length Y) 1))
      (format #t "~A, " (reverse (array-ref dp i j))))))
```

出力結果はこうなる。

```Scheme
gosh>
(), (), (), (), (), (), (), 
(), (), (), (), (), (), (), 
(), (), (), (), (), (), (), 
(), (a), (a), (a), (a), (a), (a), 
(), (a), (a b), (a b), (a b), (a b), (a b), 
(), (a), (a b), (a b c), (a b c), (a b c), (a b c), 
(), (a), (a b), (a b c), (a b c), (a b c), (a b c u), 
(), (a), (a b), (a b c), (a b c), (a b c), (a b c u), 
(), (a), (a b), (a b c), (a b c), (a b c), (a b c u), #<undef>
```

## DP配列を部分列の長さで更新していく方式

DP配列に直接部分列を詰め込んでいく方法は直観的でわかりやすいが、文字列が長くなるとメモリ効率が悪化する。そこでDP配列は長さを記録し、後から最長部分列を復元する方法が必要になる。

復元方法の説明はこちらを参考にした。

https://qiita.com/_rdtr/items/c49aa20f8d48fbea8bd2

コードを書く際はこちらを参考にした。

https://tjkendev.github.io/procon-library/python/dp/lcs.html

```Scheme
(use gauche.array)

(let* [(X (string->vector "myabcuuu"))
       (Y (string->vector "abcjju"))
       (dp (make-array (shape 0 (+ (vector-length X) 1) 0 (+ (vector-length Y) 1)) 0))
       (cache '())]

  ; CLSの処理
  (dotimes (i (vector-length X))
    (dotimes (j (vector-length Y))
      (cond [(eqv? (vector-ref X i) (vector-ref Y j))
             (array-set! dp (+ i 1) (+ j 1) (+ (array-ref dp i j) 1))]
            [else (array-set! dp (+ i 1) (+ j 1)
                              (max (array-ref dp (+ i 1) j)
                                   (array-ref dp i (+ j 1))))])))

  ; 出力
  (dotimes (i (+ (vector-length X) 1))
    (format #t "~%")
    (dotimes (j (+ (vector-length Y) 1))
      (format #t "~A, " (array-ref dp i j))))

  ; 最長共通部分列の復元 
  (let loop [(i (vector-length X))
             (j (vector-length Y))]
    (cond [(or (<= i 0) (<= j 0))
           (format #t "~%~A, " (list->string cache))]
          [(eqv? (vector-ref X (- i 1)) (vector-ref Y (- j 1)))
           (set! cache (cons (vector-ref X (- i 1)) cache))
           (loop (- i 1) (- j 1))]
          [(= (array-ref dp i j) (array-ref dp (- i 1) j))
           (loop (- i 1) j)]
          [(= (array-ref dp i j) (array-ref dp i (- j 1)))
           (loop i (- j 1))])))
```

CLSの処理途中で、X[i]とY[j]が等しいときにcacheに詰め込んでいけばよくないか？　と思ったがそういうもんでもなかった。

出力結果はこうなる。

```Scheme
gosh> 
0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 
0, 1, 1, 1, 1, 1, 1, 
0, 1, 2, 2, 2, 2, 2, 
0, 1, 2, 3, 3, 3, 3, 
0, 1, 2, 3, 3, 3, 4, 
0, 1, 2, 3, 3, 3, 4, 
0, 1, 2, 3, 3, 3, 4, 
abcu#<undef>
```
# CODE FESTIVAL 2015 あさぷろ Middle-B-ヘイホー君と削除

平方な文字列とは、前半部分と後半部分で共通な文字列が現れる文字列である。元の文字列から何個か文字を除いて平方な文字列を作る、という作業を逆に考えると、とある文字列を2つ連結し、そこに何個か文字を加えて元の文字列を作る、という手順になる。とある文字列とは元の文字列に含まれる最長共通部分列であり、元の文字列から最長な平方な文字列を取り出すには、適当な位置で元の文字列を分割し、前半部と後半部に含まれる最長共通部分列を求めればよい。

ACコードは下記。

https://atcoder.jp/contests/code-festival-2015-morning-middle/submissions/23818558