文字列とオートマトン

全位置を一つずつ確かめるより速く文字列を照合・比較するための、定番のアルゴリズムです。KMP と Z アルゴリズムはパターンを線形時間で見つけ、Manacher は回文を見つけ、ローリングハッシュは部分文字列どうしを定数時間で比較できます。

9 章 31 問で、いちばん小さな問題集です。KMP、Z アルゴリズム、Manacher、ローリングハッシュ、最小回転、Aho-Corasick、接尾辞配列と接尾辞オートマトン、部分列オートマトン、発展テクニックの順に並んでいます。解説でこれらの名前を見かけて、実際の問題で手を動かしてみたい人に向いています。