Z-algorithmの追加

[noss3885]

長さ n の文字列 s に対して、s[0,n) と s[i,n) の最長共通接頭辞(Longest Common Prefix)の長さ z[i] の配列を求める。

計算量

O(n)

参考資料

• https://github.com/atcoder/ac-library/blob/master/atcoder/string.hpp (CC0)
• https://github.com/kth-competitive-programming/kactl/blob/main/content/strings/Zfunc.h (CC0)
• https://snuke.hatenablog.com/entry/2014/12/03/214243

テスト問題

• https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_B
• https://judge.yosupo.jp/problem/zalgorithm

[noss3885]

書きます