文字列の頭良い感じの線形アルゴリズムたち

この記事はAdvent Calendar 2014の12/1の記事として書かれました。 はじめに KMP、Manachar、Z algorithm の3つについて書きたいと思います。 1アルゴリズム/1日で追記して行きます。これらのアルゴリズムでは「求めたいものの特性を生かして、既に計算した結果を上手に利用する」という…