Let's write β

プログラミング中にできたことか、思ったこととか

HaskellでLCS

特に何もなくパターンマッチでやってます。
メモ化はまだ勉強中。

lcsLen :: (Eq a) ⇒ Int →  Int →  [a] →  [a] →  Int
lcsLen _ 0 _ _ = 0
lcsLen 0 _ _ _ = 0
lcsLen i j seq1 seq2 
    | lastSeq1 ≡ lastSeq2 = 1 + lcsLen (i - 1) (j - 1) nextSeq1 nextSeq2
    | otherwise = max (lcsLen (i-1) j nextSeq1 nextSeq2)
                     (lcsLen i (j-1) nextSeq1 nextSeq2)
    where
        nextSeq1 = init seq1
        nextSeq2 = init seq2
        lastSeq1 = last seq1
        lastSeq2 = last seq2

lcs :: (Eq a) ⇒   [a] →  [a] →  Int
lcs seq1 seq2 = lcsLen seq1Len seq2Len seq1 seq2
    where
        seq1Len = length seq1
        seq2Len = length seq2
        
main = do
    putStrLn $ show $ lcs "Hoge" "Moge"