【ゼットアルゴリズム】
Zアルゴリズム とは？
公開:
💡 途中からでも、先頭と何文字そろうかを数える
文字列の各位置から、文字列全体の先頭と何文字一致するかを線形時間で求めるアルゴリズム。パターンと本文をつなげると文字列検索にも使える。
📌 このページのポイント
ひよこ Z配列には何が入るの？
ペンギン先生 各位置からの文字列が、全体の先頭と何文字続けて一致するかだよ。aabcaabなら、0始まりの位置4からはaabで、先頭のaabと3文字一致する。だからZ[4]は3になるんだ。
ひよこ 全部の位置で最初から比べるの？
ペンギン先生 ひよこ それがどう検索につながるの？
ペンギン先生 ひよこ Z[0]はどう数えるの？
もっと詳しく知りたい人へ
区切り記号や文字の単位には注意が必要ですか？
区切りにはパターンにも本文にも含まれない記号を使います。使える文字が制限されるなら、文字以外の番兵値を持つ配列にする方法もあります。バイト・コード単位・コードポイントなど、比較する単位と返す位置の単位も統一します。
まとめ：ざっくりこれだけ覚えればOK！
「Zアルゴリズム」って出てきたら「各位置と先頭の一致長を、重複比較を減らして求める方法」と思えればだいたいOK！