Z-Box 简介
你很可能因为以下两个原因之一找到了这篇文章：
- 要么你没听说过 Z-Box，想知道它们是否能以某种方式帮助你
- 要么你必须学习 Z-Box，而你完全不知道如何理解数学定义。
无论哪种方式，我们将研究 Z-Box - 不是使用一堆公式而是使用示例和 Python 代码。
什么是 Z-Box？
如果你在讲座中听说过 Z-Box 或在书中读到过它们，你可能遇到过
$$\begin{array}{ll}(1)&\;\text{Let }s:=s_0\cdots s_{n-1}\in\Sigma^n\\(2)&\;\forall i\in\{1\cdots n-1\}:\;Z_i:=max\{j\in[0\cdots n]: s_i\cdots s_{i+j-1}=s_0\cdots s_{j-1}\}\\(3)&\;\text{Z-Box starting at position i}:=s_i\cdots s_{i+Z_i-1}\,\text{if }Z_i\neq0\end{array}$$但说实话。这些定义主要针对已经理解其含义的人。对大多数学生来说，这对理解算法没有太大帮助。
不管怎样，让我们分解它，看看能挽救什么。
$(1)$ 这只是说 $s$ 是长度为 $n$ 的字符串（使用此定义）。技术上 $\Sigma$ 是字符串的字母表 - 但对于所有实际意图和目的，这由编程上下文定义，所以我们忽略 $\Sigma$。
所以假设 $n=6$。那么以下每个都符合定义：
s = "abc123"
s = "fo bar"
s = " "
s = "abcabc"在几乎所有处理字符串的算法定义中，你会发现类似的定义。
$(2)&(3)$ 稍微复杂一些。我将先不讨论定义来解释它。
这是简单的部分：从位置 i 开始的 Z-Box 只是 s 的子字符串，从位置 $i$ 开始。$Z_i$ 是其长度。
不幸的是，困难的部分是它不只是从位置 $i$ 开始的任何子字符串。但我们如何检查 Z-Box 是否有效？
让我们看看一段 Python 代码片段：
def is_valid_zbox(s, i, zi):
# zi 是 zbox 的长度，计算 zbox
zbox = s[i:i + zi]
# 计算相同长度的前缀
prefix = s[0:zi]
return zbox == prefix
is_valid_zbox("abcabc", 2, 2) # "ca" != "ab" => False
is_valid_zbox("abcabc", 2, 3) # "cab" != "abc" => False
is_valid_zbox("abcabc", 3, 2) # "ab" == "ab" => True
is_valid_zbox("abcabc", 3, 3) # "abc" == "abc" => True所以如果两个字符串相等，Z-Box 就是有效的：Z-Box 本身和 s 的前缀。
正如我们在示例中看到的，在任何位置 $i$ 可以有多个有效的 Z-box。我们使用哪一个？
由于 $(2)$ 中的 max，我们总是使用最长的一个。
简单的 Z-Box 算法
以下是如何使用我们目前所知计算 Z-box：
def is_valid_zbox(s, i, zi):
# zi 是 zbox 的长度，计算 zbox
zbox = s[i:i + zi]
# 计算相同长度的前缀
prefix = s[0:zi]
return zbox == prefix
def zbox(s, i):
# 从位置 i 开始的子字符串的最大长度
# （s 只有这么多字符）
maxlen = len(s) - i
# 尝试每个 zbox，从最长的开始
# 即 maxlen, maxlen-1, ..., 1
for zi in range(maxlen, 0, -1):
if is_valid_zbox(s, i, zi):
# 返回第一个有效的 zbox
# 由于我们从最长的开始，
# 这总是最长的 zbox
zbox = s[i:i + zi]
return zbox
# 计算 zbox
s = "abcabc"
[zbox(s, i) for i in range(1, len(s))]
# [None, None, 'abc', None, None]为什么结果中有这么多 None 值？因为正如你在字符串中看到的，a，字符串中的第一个字符，只在位置 3 再次出现。
为什么我们只计算从 $[1\cdots n-1]$ 开始的 Z-box？我们也可以为 $[0\cdots n-1]$ 计算！？！？ 但是如果你取 $s$ 的任何长度为 $j$ 从 0 开始的子字符串，并将其与 $s$ 的长度为 $j$ 的前缀比较 - 它们是相同的，无论多长！这是因为 $s$ 的长度为 $j$ 的前缀就是从 0 开始的长度为 $j$ 的 $s$（pre 意为之前，因此我们从 0 开始！）
让我们看看另一个示例：
# 计算 zbox
s = "ananas"
[zbox(s, i) for i in range(1, len(s))]
# [None, 'ana', None, 'a', None]还有一些示例我们找不到任何 Z-box！
# 计算 zbox
s = "foobar"
[zbox(s, i) for i in range(1, len(s))]
# [None, None, None, None, None]但对于某些我们可以找到很多！
# 计算 zbox
s = "abaabaabab"
[zbox(s, i) for i in range(1, len(s))]
# [None, 'a', 'abaaba', None, 'a', 'aba', None, 'ab', None]额外阅读：
另一篇关于 Z-box 的易于理解的博客文章，包含更高效的算法
讲座类型材料：
https://www.bio.ifi.lmu.de/mitarbeiter/volker-heun/notes/ab6.pdf section 2.5.1 https://www.informatik.hu-berlin.de/de/forschung/gebiete/wbi/teaching/archive/ws0506/bioinformatik/03_zbox.pdf