Z algorithm

Z algorithmを図に頼らずに理解したかったので書きました． 長さの文字列にZ algorithmを適用することを考えます． 以下の説明では文字列中の各文字を0-basedで指定します1．の文字目をと表記します．また，の文字目から文字目までを取り出した部分文字列をと表記します．のときは空文字列とし，空文字列同士は一致するとします．便宜上を任意の文字に一致しない文字と取り決めます． に対し，をかつを満たす以下の非負整数とします．つまり，はとの最長共通接頭辞の長さを表します．なのでです． 以下，とし，あるについてが既知であるとします．また，とします．の定義より，かつです． について，この順に…