Z算法背后的直觉

Question

Z算法是一种时间复杂度为O(n)的字符串匹配算法。

一个使用案例是从字符串B中查找字符串A的最长出现次数。例如，从字符串"stackoverflow"中查找"overdose"的最长出现次数将是"over"。你可以通过使用组合字符串"overdose#stackoverflow"（其中#是两个字符串中都不存在的字符）调用Z算法来发现这一点。然后，Z算法会尝试将组合字符串与自身进行匹配，并创建一个数组z[]，其中z[i]给出从索引i开始的最长匹配长度。在我们的示例中：

index  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21
string o  v  e  r  d  o  s  e  #  s  t  a  c  k  o  v  e  r  f  l  o  w
z    (21) 0  0  0  0  1  0  0  0  0  0  0  0  0  4  0  0  0  0  0  1  0

有很多代码实现和面向数学的算法解释，以下是一些很好的例子：

http://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/ http://codeforces.com/blog/entry/3107

我知道这个算法怎么工作，但是我不理解为什么。它似乎几乎像黑魔法一样。我非常强烈地感觉这个任务应该需要O(n^2)的时间，然而这里却有一个只需要O(n)的算法。

- Atte Juvonen

---

这是一种优美的算法，隐藏了许多复杂性。你提供的那些参考资料不好。我查看了几个其他的文献，包括大学课程的幻灯片集，也都相当糟糕。试试这个链接，并结合一些示例来理解它的解释。https://ivanyu.me/blog/2013/10/15/z-algorithm/ - Gene

Answer 1

我也不完全觉得它很直观，所以我认为我有资格回答。否则的话，我会说你不理解因为你是个白痴，但这肯定不是你希望得到的答案 :-)

实例（来自解释）：

Correctness is inherent in the algorithm and is pretty intuitively clear.

所以，让我们尝试更加直观地理解...首先，我猜测O(n^2)的普遍直觉是：对于长度为N的字符串，如果你在没有其他信息的情况下随机落在字符串中的某个位置i，你需要匹配x（<N）个字符才能计算Z[i]。如果你重复这个过程N次，你最多需要进行N(N-1)次测试，因此时间复杂度为O(n^2)。

然而，Z算法充分利用了你从过去的计算中获得的信息。

让我们看看。

首先，只要你没有匹配（Z[i]=0），你就可以沿着字符串向前移动一个字符进行一次比较，所以时间复杂度为O(N)。

其次，当你找到一个范围内有匹配项的区域（在索引i处），诀窍是使用前面的Z[0...i-1]来进行巧妙的推断，以在该范围内恒定的时间内计算出所有的Z值，而不需要在该范围内进行其他比较。下一个匹配项将仅在该范围的右侧进行。

这就是我理解的方式，希望对你有所帮助。

- Ilya

Answer 2

我一开始是为了更深入地理解这个算法而找到了这个问题。

最初，我对codeforces post并不理解，但后来发现它足够好理解，并且我注意到该帖子并不完全准确，还省略了一些思维过程中的步骤，使得它有点令人困惑。

让我尝试纠正那篇帖子中的错误，并澄清一些我认为可能有助于人们串联起来的步骤。在这个过程中，我希望我们可以从原作者那里学习一些直觉。在解释中，我将混合一些来自codeforces和我的个人注释的引用块，以便将原始帖子与我们的讨论保持紧密联系。

Z算法的开始：

当我们迭代字符串中的字母（索引i从1到n-1）时，我们维护一个区间[L，R]，该区间具有最大的R，使得1≤L≤i≤R且S [L ... R]是前缀子字符串（如果不存在这样的区间，则只需让L = R = -1）。对于i = 1，我们可以通过将S [0 ...]与S [1 ...]进行比较来简单地计算L和R。此外，我们还会在此期间获得Z1。

这很简单明了。

现在假设我们已经有了正确的区间[L，R]，用于i-1和所有Z值直到i-1。我们将通过以下步骤计算Z [i]和新的[L，R]：

• 如果i > R，则不存在一个以i为起点且以i或之后的位置为终点的前缀子串。 如果存在这样的子串，则[L，R]将是该子串的区间，而不是其当前值。因此，我们“重置”并通过比较S [0 ...]和S [i ...]来计算新的[L，R]，同时获得Z [i]（Z [i] = R-L + 1）。

项目符号中的粗体部分可能会让人感到困惑，但如果您读两遍，它实际上只是重复了R的定义。

否则，i ≤ R，因此当前的[L，R]至少延伸到i。令k = i-L。我们知道Z [i]≥min（Z [k]，R-i + 1），因为S [i ...]与S [k ...]匹配至少R-i + 1个字符（它们在[L，R]间隔内，我们知道它是前缀子字符串）。现在我们有几种情况需要考虑。

粗体部分不完全准确，因为R-i + 1可以大于Z [k]，在这种情况下，Z [i]将为Z [k]。

现在让我们关注关键点：Z[i] ≥ min(Z[k], R-i+1)。这是为什么呢？因为以下原因：

• 基于区间[L，R]的定义和i≤R，我们已经确认S[0...R-L]==S[L...R]，因此S[0...k]==S[L...i]，并且S[k...R-L]==S[i...R];
• 假设Z[k]=x，根据Z的定义，我们知道S[0...x]==S[k...k+x];
• 结合上述方程，我们知道当x

这些是我在开头提到的缺失的部分，它们解释了第二和第三个要点，以及部分最后一个要点。当我阅读codeforces帖子时，这并不直观。对我来说，这是算法中最重要的部分。

对于最后一个要点，如果Z[k] ≥ R - i + 1，则使用i作为新的L，并将R扩展到更大的R'来刷新[L，R]。

在整个过程中，Z算法仅使用每个字符一次进行比较，因此时间复杂度为O（n）。

正如Ilya所回答的，该算法的直觉是精心地重复利用我们迄今收集到的每个信息片段。我只是用另一种方式解释了它。希望能有所帮助。

- Kun Hu