文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

この記事はAdvent Calendar 2014の12/1の記事として書かれました。 はじめに KMP、Manachar、Z algorithm の３つについて書きたいと思います。 １アルゴリズム／１日で追記して行きます。 これらのアルゴリズムでは「求めたいものの特性を生かして、既に計算した結果を上手に利用する」という点で共通しており、いずれも「なるほどなぁ」と言わされました。 この美しいアルゴリズムたちを是非紹介したいと思い、この記事を書くことにしました。 ・記法について |S|：文字列 S の長さを表す。 S[i,j]：文字列 S の i 文字目から j 文字目までを取り出した文字列を表す。 KMP ※これは正確にはKMPではなくMPです。KMPについてはこちら。 文字列 S が与えられたときに、各 i について「文字列S[0,i-1]の接頭辞と接尾辞が最大何文字一致しているか」を記