Z 函数 / 扩展 KMP-JZTXT

前置

\(KMP\)：\(O(n)\) 求解字符串匹配的算法。维护前缀数组 \(p_i\) 表示字符串 \(s\) 以 \(i\) 结尾的最长公共前后缀的长度；
\(border\): 对于字符串 \(s\)，如果存在一个子串 \(t\) 满足 \(t\) 既是 \(s\) 的一个前缀又是 \(s\) 的后缀，则称 \(t\) 是 \(s\) 的一个 border;

Z函数

定义：\(z_i\) 表示字符串 \(s\) 下标从 \(i\) 开始的后缀与 \(s\) 的最长公共前缀 (\(LCP\)) 的长度。这里我们规定字符串下标从 \(0\) 开始。

e.g.

\(\ s: a\ a\ a\ a\ b\ a\ a\ b\)

\(\ i:\ 0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\)

\(z_i: 8\ 3\ 2\ 1\ 0\ 2\ 1\ 0\)

注意，在处理不同的问题时 \(z_0\) 通常为 \(\vert s\vert\) 或 \(0\)。

对于字符串 \(s\) 的下标 \(i\)，如果有 \(Z_i\neq 0\)，那么称区间 \([i,i+z_i-1]\) 为一个 \(Z-box\)（匹配段）。

考虑如何实现求解Z函数。假定区间 \([l, r]\) 为找到的 \(Z-box\) 中 \(r\) 最靠右的哪一个匹配段，当前在考虑第 \(i\) 个位置。

若 \(i>r\)，则从下标 \(0\) 开始暴力匹配；
若 \(i\le r\)，
- 若 \(i-z_{i-l} - 1 < r\)，那么有 \(z_i=z_{i-l}\)；
- 若 \(i-z_{i-l}-1 \ge r\)，暴力匹配

在每找到一个一个 \(Z-box\)，更新 \(l=i,r=i+z_i-1\)。

单次暴力扩展至少使右端点 \(+1\)，故暴力匹配的总时间是 \(O(n)\) 的。

对于 \(i-z_{i-l}-1 < r\) 的情况。由于 \([l,r]\) 是一个 \(Z-box\)，所以 \(s[0,r-l]=s[l,r]\)，同时因为 \(l\le i\le r\)，有 \(s[i - l, r - l+1]=s[i,r]\)。这时候 \(z_i\) 就相当于是 \(z_{i-l}\)，直接转移即可。

总时间复杂度 \(O(n)\)。

void Solve(string s) {
  z[0] = n = s.size();
  for(int i = 1, l = 0, r = 0; i < n; i++) {
    if(z[i - l] < r - i + 1) {
      z[i] = z[i - l];
    } else {
      for(z[i]= max(0, r - i + 1); i + z[i] < n && s[z[i]] == s[i + z[i]]; z[i]++) { // 暴力扩展
      }
      l = i, r = i + z[i] - 1;
    }
  }
}

应用

给定字符串 \(s,t\)，求出 \(s\) 的每一个后缀与 \(t\) 的最长公共前缀。

sol: 构造字符串 \(t+特殊字符+s\)，然后求z函数即可。
求字符串 \(s\) 的所有 \(border\)。

sol: 对于每一个位置 \(i\)，如果有 \(i+z_i=\vert s\vert\)，则当前以 \(i\) 开头的 \(Z-box\) 是一个 \(border\)。
求字符串 \(s\) 的每一个前缀的出现次数。

sol: 对 \(z_i\) 的长度维护后缀和。因为对于位置 \(i\)，若 \(z_i \ne 0\)，则长度在 \([1,z_i]\) 内的前缀均出现了一次。