Z algorithm

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /z-algorithm#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /z-algorithm#noredirect を利用してください。
name
Z algorithm
short description
Z algorithm とは、与えられた文字列 $S$ に対して、文字列 $S$ の $i$ 文字目以降の文字列 $S\lbrack i \colon \rbrack = (S _ i, S _ {i + 1}, \dots, S _ {\vert S \vert - 1})$ を考えたときの、すべての $i$ について「$S$ と $S\lbrack i \colon \rbrack$ の最長共通接頭辞の長さ」をまとめて $O(\vert S \vert)$ で求めるアルゴリズムのひとつ。