2026-11-02
Common.hs
lcs :: String -> String -> String
lcs xs'@(x : xs) ys'@(y : ys)
| x == y = x : lcs xs ys'
| otherwise = longer (lcs xs' ys) (lcs xs ys')
where
longer a b = if length a >= length b then a else b
lcs _ _ = ""
main :: IO ()
main = putStrLn (lcs "aab" "ab")
lcs は、2つの文字列のどちらからも、文字をいくつか取り除いて残りを元の順に並べれば作れる文字列のうち、最も長いものを返すつもりの関数です。取り除く文字は飛び飛びでかまいません。lcs "aab" "ab" は本来 ab を表示するはずが、いまは "ab" より長い aab を表示します。
Answer
Wrong
| x == y = x : lcs xs ys'
先頭の文字が一致したとき、xs だけを進め、ys には一致した y を含む ys' をそのまま渡しています。y は使い終わっていないことになり、xs の次の文字とまた一致できます。lcs "aab" "ab" では、"aab" の1文字目と2文字目の 'a' が、どちらも "ab" の同じ 'a' と一致し、続く 'b' も一致して "aab" ができます。
共通部分の文字は、どちらの列でも別々の位置から1回ずつ取る必要があり、"aab" は "ab" からは作れません。結果が ys より長くなったのはこのためです。xs に同じ文字が並ばない入力では、残した y と再び一致する文字が来ないので、このバグは表に出ません。
Right
| x == y = x : lcs xs ys
一致した x と y は、結果の1文字として両方の列で使ったので、両方を1つずつ進めます。一致したときは両方を進めても最長を逃さず、longer で2通りを比べる必要もありません。lcs "aab" "ab" は1文字目の 'a' どうしを使ったあと lcs "ab" "b" に進み、"ab" を返します。1
- 先頭どうしが一致したとき、最長の共通部分の1文字目を、先頭の
xとyの組に取り替えても、残りの文字はどちらの列でもそれより後ろの位置で組んでいるので、共通部分のままで長さも変わりません。そのため、先頭どうしを使う最長の共通部分が必ずあります。