Namaran

Code daily. Without assist.

2026-11-02

LcsRow.hs

nextRow :: String -> [Int] -> Char -> [Int]
nextRow ys prev x = scanl step 0 (zip3 ys prev (drop 1 prev))
 where
  step left (y, diag, up)
    | x == y = diag + 1
    | otherwise = max left up

main :: IO ()
main = print (foldl (nextRow "bab") [0, 0, 0, 0] "ab")

これは何を出力するでしょうか?

Answer

[0,1,1,2] です。

foldl は初期値 [0,0,0,0] から始めて、"ab" の文字 'a'、'b' の順に nextRow "bab" を適用します。nextRow の中では、zip3 が ys の文字 y と、前の行の要素 diag、その1つ右の要素 up を組にします。scanl は先頭に0を置き、組ごとに step で次の要素を作ります。left は scanl が直前に作った要素なので、新しい行の左隣です。

'a' の行では、y が 'b' のときは max 0 0 で0、'a' のときは一致するので diag + 1 で1、次の 'b' では max 1 0 で1になり、[0,0,1,1] ができます。'b' の行では、最初の 'b' が一致して 0 + 1 = 1、'a' は max 1 1 で1、最後の 'b' が一致して、前の行の3番目の1に1を足した2になります。

この表は、2つの文字列から順番を保ったまま、飛び飛びでもよいので共通に取り出せる最も長い列の長さを数えています。最後の行の j 番目は、"ab" と "bab" の先頭 j 文字の間でのその長さで、"ab" 全体と "bab" 全体なら "ab" の2です。zip3 は3つのうち最も短い drop 1 prev と ys に合わせて3組だけ作るので、scanl の先頭の0と合わせて、どの行も長さ4のまま進みます。