第5章 文字列の照合

5.2 正規表現によるパターンマッチング

KMPのアルゴリズムを良くみると、入力が戻らない（1方向）である。
⇒決定性有限オートマトンができるんじゃない？
マッチングオートマトンという。
本質的にはKMPアルゴリズムと同じもの
マッチングオートマトンは正規表現に対応する。
正規表現で表されるものは必ず有限オートマトンで処理できる。
現実的には、小さい決定性オートマトンが作れないとうまくいかないっぽい。

5.3 最長共通部分列(longest common subsequence)

2つの文字列の最長共通部分列を抜き出す。
動的計画法（DP）を用いる。

直前の3つの値から判断できるということ。
最終的にlcdlcs(n,m)が求まればよい。