問題概要
2 つの文字列 $S, T$ が与えられる．$S$ の文字をいくつか変更することで $S$ の（連続する）部分文字列が $T$ に一致するようにしたい．最小で何文字を変更する必要があるか？
制約
- $1 \leq |S|, |T| \leq 1{,}000$
解法
$S$ のどの位置を $T$ に一致させるかを固定すれば，ループと比較で変更するべき文字数を数えることができます．従って，部分文字列のとり方（開始位置）をすべて試して，そのそれぞれについてループで一致しない文字数を数えて最小値をとることで問題を解くことができます．
コード
main = do s <- getLine t <- getLine let ss = filter ( ( == length t ) . length ) $ map ( take $ length t ) $ tails s print $ minimum $ map ( solve t ) ss solve s t = length $ filter id $ zipWith (/=) s t
