Z Algorithm
(src/string/Zalgorithm.hpp)

• View this file on GitHub
• Last update: 2024-05-31 19:00:40+09:00
• Include: #include "src/string/Zalgorithm.hpp"

• 参考実装：KACTL

使い方

• vector<ll> Z(string s)：$Z[i] := \text{LCP}(s, s[i:])$ で定義される配列 $Z$ を求める
  • $O(n)$ 時間

使い方 (応用編)

• 文字列 $s$ の部分文字列に $t$ が現れるか判定：$\text{Z}(t + s)$ の後ろ $\text{sz}(s)$ 個に $\text{sz}(t)$ 以上があるか
• 文字列 $s$ の最小周期：$\text{Z}(s + s)$ の $1$ 要素目以降で，はじめて $\text{sz}(s)$ 以上が出現する位置

Verified with

• test/string/Zalgorithm.test.cpp

Code

// Z[i] := LCP(s, s[i:])
// abacaba -> 7010301
auto Z(string s) {
   ll n = sz(s), l = -1, r = -1;
   vector<ll> z(n, n);
   rep(i, 1, n) {
      ll& x = z[i] = i < r ? min(r - i, z[i - l]) : 0;
      while(i + x < n && s[i + x] == s[x]) x++;
      if(i + x > r) l = i, r = i + x;
   }
   return z;
}

#line 1 "src/string/Zalgorithm.hpp"
// Z[i] := LCP(s, s[i:])
// abacaba -> 7010301
auto Z(string s) {
   ll n = sz(s), l = -1, r = -1;
   vector<ll> z(n, n);
   rep(i, 1, n) {
      ll& x = z[i] = i < r ? min(r - i, z[i - l]) : 0;
      while(i + x < n && s[i + x] == s[x]) x++;
      if(i + x > r) l = i, r = i + x;
   }
   return z;
}

Back to top page