第5章 文字列の照合

ストリングマッチング
単純に考えると、n文字の文字列からm文字を探索するにはO(nm)の時間がかかる。
→KMPアルゴリズム・BMアルゴリズム：O(n+m)で実行できる

KMPアルゴリズム

2DPDA：2方向決定性オートマトン

前後に動く＆スタックがある。
定理：RAMは2DPDAを線形時間で模倣できる
できるらしい。重要らしい。
実際に実装したのがKMPアルゴリズム（BMも）