2026-11-02
LcsLength.hs
import Data.Array
lcsLength :: (Eq a) => [a] -> [a] -> Int
列 xs から要素をいくつか取り除き、残りを元の順に並べたものを xs の部分列と呼びます。取り除く要素は飛び飛びでもかまいません。xs と ys のどちらの部分列でもある列のうち、最も長いものの長さを返す lcsLength を書いてください。どちらかが空なら0です。長さ2000の列どうしでも、数秒以内に答えが出るようにします。
入力例 1
lcsLength "abcbdab" "bdcaba"
出力例 1
4
入力例 2
lcsLength [1,2,3] [3,2,1]
出力例 2
1
入力例 3
lcsLength "abc" ""
出力例 3
0
Reference
import Data.Array
lcsLength :: (Eq a) => [a] -> [a] -> Int
lcsLength xs ys = table ! (0, 0)
where
n = length xs
m = length ys
xa = listArray (0, n - 1) xs
ya = listArray (0, m - 1) ys
table = array ((0, 0), (n, m)) [((i, j), cell i j) | i <- [0 .. n], j <- [0 .. m]]
cell i j
| i == n || j == m = 0
| xa ! i == ya ! j = 1 + table ! (i + 1, j + 1)
| otherwise = max (table ! (i + 1, j)) (table ! (i, j + 1))
main :: IO ()
main = do
print (lcsLength "abcbdab" "bdcaba")
print (lcsLength "abc" "")
print (lcsLength [1, 2, 3] [3, 2, 1 :: Int])
print (lcsLength (replicate 2000 'a') (replicate 2000 'a'))
xs の i 番目以降と ys の j 番目以降の答えを cell i j とすると、cell i j は先頭の2要素と、添字を1つ進めた (i + 1, j + 1)、(i + 1, j)、(i, j + 1) の答えから決まります。これを再帰呼び出しでそのまま書くと、同じ (i, j) を何度も計算し直すので、長さ2000では終わりません。
すべての (i, j) の答えを配列 table に入れ、cell は再帰呼び出しの代わりに table の要素を読みます。array は要素を評価せずに、まだ計算していない式のまま配列に入れるので、table の要素が table のほかの要素を参照していてもかまいません。table ! (0, 0) が要ると、その式が参照する要素が初めて計算され、計算した値は配列に残るので、どの要素も1回しか計算されません。どの順に表を埋めるかを書く必要はなく、参照の関係から順番が決まります。
表は n 行目と m 列目まで作ります。そこは空の列が相手になる場所で、答えは0です。添字を xa ! i で引くのは i < n かつ j < m のときだけなので、入力例3のように片方が空でも範囲の外は読みません。表は (n + 1)(m + 1) 個の要素を持つので、2000 × 2000 でも約400万回の計算で済みます。
掲載したのは参考実装で、唯一の正解ではありません。表を1行ずつ、前の行から scanl で作っていく書き方なら、前の行だけを持てばよいので、使うメモリも少なくなります。