src/String/ZAlgorithm.hpp
概要
文字列s[0:]とs[i:]の共通prefixの長さの配列を返す、O(|s|)。
基本的なアイディアは、以前に先頭からの文字列との共通prefixとして計算された値を使い回すこと。
左から順に求める配列aを計算しながら、それまでに一番右まで到達した部分についてaをもう一度たどると先頭とのprefix一致がショートカットできる。
アルゴリズム参考: https://snuke.hatenablog.com/entry/2014/12/03/214243
実装のrm_idx(rightmost index)は、それまでに共通prefixとして一番右まで到達したときのインデックスを表す。
苦労して結構うまく実装できたと思ったらsnukeさんのコードとほとんど同じだった、完…
Verified with
Code
Back to top page