From 1a15da7ad0a4e1c742befbed0e660dc099089df8 Mon Sep 17 00:00:00 2001
From: LeoJacob <lzy4575@126.com>
Date: Sat, 3 Nov 2018 22:44:35 +0800
Subject: [PATCH] feat: add Z function page

Add a Chinese version of Z function page originated from e-maxx. It is translated from its english version.
---
 docs/string/z-function.md | 206 ++++++++++++++++++++++++++++++++++++++++++++++
 mkdocs.yml                |   1 +
 2 files changed, 207 insertions(+)
 create mode 100644 docs/string/z-function.md

diff --git a/docs/string/z-function.md b/docs/string/z-function.md
new file mode 100644
index 00000000..6c39cd23
--- /dev/null
+++ b/docs/string/z-function.md
@@ -0,0 +1,206 @@
+假设我们有一个长度为 $n$ 的字符串 $s$。该字符串的**Z 函数**为一个长度为 $n$ 的数组，其中第 $i$ 个元素为满足从位置 $i$ 开始且为 $s$ 前缀的字符串的最大长度。
+
+换句话说，$z[i]$ 是 $s$ 和从 $i$ 开始的 $s$ 的后缀的最大公共前缀长度。
+
+**注意**：为了避免歧义，在这篇文章中下标从 $0$ 开始，即 $s$ 的第一个字符下标为 $0$，最后一个字符下标为 $n - 1$。
+
+Z 函数的第一个元素，$z[0]$，通常不是良定义的。在这篇文章中我们假定它是 $0$（虽然在算法实现中这没有任何影响）。
+
+这篇文章包含在 $O(n)$ 时间复杂度内计算 Z 函数的算法以及其各种应用。
+
+## 样例
+
+下面若干样例展示了对于不同字符串的 Z 函数：
+
+- $Z(\mathtt{aaaaa}) = [0, 4, 3, 2, 1]$
+- $Z(\mathtt{aaabaab}) = [0, 2, 1, 0, 2, 1, 0]$
+- $Z(\mathtt{abacaba}) = [0, 0, 1, 0, 3, 0, 1]$
+
+## 朴素算法
+
+Z 函数的形式化定义可被表述为下列基础的 $O(n^2)$ 实现。
+
+```c++
+vector<int> z_function_trivial(string s) {
+    int n = (int) s.length();
+    vector<int> z(n);
+    for (int i = 1; i < n; ++i)
+        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
+            ++z[i];
+    return z;
+}
+```
+
+我们做的仅仅为循环每个位置 $i$，并通过下述做法更新每个 $z[i]$：从 $z[i] = 0$ 开始，只要我们没有失配（并且没有到达末尾）就将其加 $1$。
+
+诚然，这并不是一个高效的实现。我们接下来将展示一个高效实现的构造过程。
+
+## 计算 Z 函数的高效算法
+
+为了得到一个高效算法，我们将以 $i = 1$ 到 $n - 1$ 的顺序计算 $z[i]$，但在计算一个新值的同时，我们将尝试尽最大努力使用之前已经计算好的值。
+
+为了简便起见，定义**匹配段**为同 $s$ 一个前缀相同的那些子串。举例来说，所求 Z 函数的第 $i$ 个元素 $z[i]$ 为从位置 $i$ 开始的匹配段的长度（其终止位置位于 $i + z[i] - 1$）。
+
+为了达成目标，我们将始终保持**$[l;r]$  为最靠右的匹配段**。也就是说，在所有已探测到的匹配段中，我们将保持结尾最靠右的那一个。另一方面，下标 $r$ 可被认为是字符串 $s$ 已被算法扫描的边界；任何超过该点的字符都是未知的。
+
+假设当前下标为 $i$（即我们要计算的下一个 Z 函数值的下标），则有两种情况：
+
+- $i > r$ -- 当前位置在我们已处理位置**之外**。
+
+  我们接下来使用**朴素算法**（即一个一个的比较字符）来计算 $z[i]$。注意如果最后 $z[i] > 0$，我们需要更新最靠右的匹配段的下标，因为新的 $r = i + z[i] - 1$ 一定比之前的 $r$ 优。
+
+- $i \le r$ -- 当前位置位于当前匹配段 $[l;r]$ 之内。
+
+  那么我们可以用已计算过的 Z 函数值来“初始化” $z[i]$ 至某值（至少比“从零开始”要好），甚至可能是某些较大的值。
+
+  为了做到这一点，我们注意到子串 $s[l\dots r]$ 和 $s[0 \dots r - l]$ 匹配。这意味着作为 $z[i]$ 的一个初始近似，我们可以直接使用对应于段 $s[0 \dots r - l]$ 的已计算过的 Z 函数值，也即 $z[i - l]$。
+
+  然而，$z[i - l]$ 可能太大了：将其应用到位置 $i$ 结果可能超过下标 $r$。这种做法并不合法，原因在于我们对 $r$ 右侧的字符一无所知：他们可能并不满足要求。
+
+  此处给出一个相似场景的**例子**：
+  
+  $$
+  s=\mathtt{aaaabaa}
+  $$
+  
+  当我们尝试计算末尾位置（$i = 6$）的值时，当前匹配的段为 $[5;6]$。位置 $6$ 会匹配位置 $6 - 5 = 1$，其 Z 函数值为 $z[1] = 3$。显然，我们不能将 $z[6]$ 初始化为 $3$，因为这完全不对。我们可以初始化的最大值为 $1$ -- 因为这是使我们不超过段 $[l;r]$ 的边界 $r$ 的最大可能取值。
+
+  因此，我们可以放心的将下列值作为 $z[i]$ 的一个初始近似：
+  
+  $$
+  z_0[i] = \min(r - i + 1, z[i - l])
+  $$
+  
+  当将 $z[i]$ 初始化为 $z_0[i]$ 后，我们尝试使用**朴素算法**增加 $z[i]$ 的值 -- 因为宏观来讲，对于边界 $r$ 之后的事情，我们无法得知段是否会继续匹配还是失配。
+
+综上所述，整个算法被划分成两种情况，他们只在设置 $z[i]$ 的**初始值**时有所不同：在第一种情况下，其被认为为 $0$，在第二种情况下它由先前已计算过的值确定（使用前述公式）。之后，该算法的两个分支都被规约为实现**朴素算法**。当我们设置完初始值后，该算法即开始执行。
+
+该算法看起来非常简单。尽管在每轮迭代都会运行朴素算法，但我们已经取得了巨大进步：获得了一个时间复杂度为线性的算法。之后我们会证明这一点。
+
+## 实现
+
+实现相对来说十分简明：
+
+```c++
+vector<int> z_function(string s) {
+    int n = (int) s.length();
+    vector<int> z(n);
+    for (int i = 1, l = 0, r = 0; i < n; ++i) {
+        if (i <= r)
+            z[i] = min (r - i + 1, z[i - l]);
+        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
+            ++z[i];
+        if (i + z[i] - 1 > r)
+            l = i, r = i + z[i] - 1;
+    }
+    return z;
+}
+```
+
+### 对该实现的注释
+
+整个解法被作为一个函数给出。该函数返回一个长度为 $n$ 的数组 -- $s$ 的 Z 函数。
+
+数组 $z$ 被初始化为全 $0$。当前最右的匹配段被假定为 $[0;0]$（一个故意为之的不包含任何 $i$ 的小段）。
+
+在循环内，对于 $i=1\dots n - 1$，我们首先确定 $z[i]$ 的初始值 -- 其要么保持为 $0$ 或者使用前述公式计算。
+
+之后，朴素算法尝试尽可能多的增加 $z[i]$ 值。
+
+最后，如果必要（即如果 $i + z[i] - 1 > r$），我们更新最右匹配段 $[l;r]$。
+
+## 算法的渐进行为
+
+我们将证明上述算法的运行时间关于字符串长度呈线性 -- 即其时间复杂度为 $O(n)$。
+
+该证明十分简单。
+
+我们只关心内层 `while` 循环，因为其余部分在一次循环中只是一堆常数次操作，其时间复杂度总和为 $O(n)$。
+
+我们将证明 `while` 的**每次迭代**都将增加匹配段的右边界 $r$。
+
+为了做到这一点，我们将考虑算法的所有分支：
+
+- $i > r$
+
+  在这种情况下，要么 `while` 循环不进行任何迭代（如果 $s[0] \neq s[i]$），要么其将从位置 $i$ 开始进行若干次迭代，其中每次迭代将向右移动一个字符。每次迭代后，右边界 $r$ 必定被更新。
+
+  因此我们证明了，当 $i > r$ 时，`while` 循环的每轮迭代都会使新的 $r$ 增加 $1$。
+
+- $i \le r$
+
+  在这种情况下，我们将 $z[i]$ 初始化为由前述公式给出的某个具体 $z_0$。将 $z_0$ 和 $r - i + 1$ 比较，可能有三种情况：
+
+  - $z_0 < r - i + 1$
+
+    我们证明在这种情况下 `while` 循环不会进行任何迭代。
+
+    这是十分容易证明的，比如通过反证法：如果 `while` 循环进行了至少一次迭代，这意味着初始近似 $z[i] = z_0$ 是不准确的（小于匹配的实际长度）。但是由于 $s[l\dots r]$ 和 $s[0\dots r - l]$ 是一样的，这推出 $z[i - l]$ 的值是错误的（比其该有的值小）。
+
+    所以，因为 $z[i - l]$ 是正确的且其值小于 $r - i + 1$，故该值同所求的 $z[i]$ 是相同的。
+
+  - $z_0 = r - i + 1$
+
+    在这种情况下，`while` 循环可能会进行若干次迭代。因为我们从 $s[r + 1]$ 开始比较，而其位置已经超过了区间 $[l;r]$，故每次迭代都会使 $r$ 增加。
+
+  - $z_0 > r - i + 1$
+
+    根据 $z_0$ 的定义，这种情况是不可能的。
+
+综上，我们已经证明了内层循环的每次迭代都会使 $r$ 向右移动。由于 $r$ 不可能超过 $n - 1$，这意味着内层循环至多进行 $n - 1$ 轮迭代。
+
+因为该算法的剩余部分显然时间复杂度为 $O(n)$，所以我们已经证明了计算 Z 函数的整个算法时间复杂度为线性。
+
+## 应用
+
+我们现在来考虑在若干具体情况下 Z 函数的应用。
+
+这些应用在很大程度上同[前缀函数](https://cp-algorithms.com/string/prefix-function.html)的应用类似。
+
+### 查找子串
+
+为了避免混淆，我们将 $t$ 称作**文本**，将 $p$ 称作**模式**。所给出的问题是：寻找在文本 $t$ 中模式 $p$ 的所有出现（occurrence）。
+
+为了解决该问题，我们构造一个新的字符串 $s = p + \diamond + t$，也即我们将 $p$ 和 $t$ 连接在一起，但是在中间放置了一个分割字符 $\diamond$（我们将如此选取  $\diamond$ 使得其必定不出现在 $p$ 和 $t$ 中）。
+
+首先计算 $s$ 的 Z 函数。接下来，对于在区间 $[0; \operatorname{length}(t) - 1]$ 中的任意 $i$，我们考虑其对应的值 $k = z[i + \operatorname{length}(p) + 1]$。如果 $k$ 等于 $\operatorname{length}(p)$，那么我们知道有一个 $p$ 的出现位于 $t$ 的第 $i$ 个位置，否则没有 $p$ 的出现位于 $t$ 的第 $i$ 个位置。
+
+其时间复杂度（同时也是其空间复杂度）为 $O(\operatorname{length}(t) + \operatorname{length}(p))$。
+
+### 一个字符串中本质不同子串的数目
+
+给定一个长度为 $n$ 的字符串 $s$，计算 $s$ 的本质不同子串的数目。
+
+我们将迭代的解决该问题。也即：在知道了当前的本质不同子串的数目的情况下，在 $s$ 末尾添加一个字符后重新计算该数目。
+
+令 $k$ 为当前 $s$ 的本质不同子串数量。我们添加一个新的字符 $c$ 至 $s$。显然，会有一些新的子串以新的字符 $c$ 结尾（换句话说，那些以该字符结尾且我们之前未曾遇到的子串）。
+
+构造字符串 $t = s + c$ 并将其反转（以相反顺序书写其字符）。我们现在的任务是计算有多少 $t$ 的前缀未在 $t$ 的其余任何地方出现。让我们计算 $t$ 的 Z 函数并找到其最大值 $z_{\max}$。显然，$t$ 的长度为 $z_{\max}$ 的前缀出现在 $t$ 中间的某个位置。自然的，更短的前缀也出现了。
+
+所以，我们已经找到了当将字符 $c$ 添加至 $s$ 后新出现的子串数目为 $\operatorname{length}(t) - z_{\max}$。
+
+作为其结果，该解法对于一个长度为 $n​$ 的字符串的时间复杂度为 $O(n^2)​$。
+
+值得注意的是，我们可以用同样的方法在 $O(n)$ 时间内，重新计算在头部添加一个字符，或者移除一个字符（从尾或者头）时的本质不同子串数目。
+
+### 字符串压缩
+
+给定一个长度为 $n$ 的字符串 $s$，找到其最短的“压缩”表示，即：寻找一个最短的字符串 $t$，使得 $s$ 可以被 $t$ 的一份或多份拷贝的拼接表示。
+
+其中一种解法为：计算 $s$ 的 Z 函数，从小到大循环所有满足 $i$ 整除 $n$ 的 $i$。在找到第一个满足 $i + z[i] = n$ 的 $i$ 时终止。那么该字符串 $s$ 可被压缩为长度 $i​$ 的字符串。
+
+该事实的证明同应用[前缀函数](https://cp-algorithms.com/string/prefix-function.html)的解法证明一样。
+
+## 练习题目
+
+- [Codeforces - Password \[Difficulty: Easy\]](http://codeforces.com/problemset/problem/126/B)
+- [UVA # 455 "Periodic Strings" \[Difficulty: Medium\]](http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=396)
+- [UVA # 11022 "String Factoring" \[Difficulty: Medium\]](http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1963)
+- [UVa 11475 - Extend to Palindrome](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2470)
+- [LA 6439 - Pasti Pas!](https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=588&page=show_problem&problem=4450)
+- [Codechef - Chef and Strings](https://www.codechef.com/problems/CHSTR)
+- [Codeforces - Prefixes and Suffixes](http://codeforces.com/problemset/problem/432/D)
+
+* * *
+
+**本页面主要译自博文 [Z-функция строки и её вычисление](http://e-maxx.ru/algo/z_function) 与其英文翻译版 [Z-function and its calculation](https://cp-algorithms.com/string/z-function.html) 。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。**
\ No newline at end of file
diff --git a/mkdocs.yml b/mkdocs.yml
index b8ff0f21..339290cf 100644
--- a/mkdocs.yml
+++ b/mkdocs.yml
@@ -79,6 +79,7 @@ nav:
     - 后缀树: string/suffix-tree.md
     - Manacher: string/manacher.md
     - 最小表示法: string/minimal-string.md
+    - Z 函数: string/z-function.md
   - 数学:
     - 数学部分简介: math/index.md
     - 进制: math/base.md
-- 
2.11.0