Z 算法背后的直觉

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

一种用例是从字符串 B 中查找字符串 A 的最长出现次数。例如，"overdose" from "stackoverflow"将会"over"。您可以通过使用组合字符串调用 Z 算法来发现这一点"overdose#stackoverflow"（其中 # 是两个字符串中都不存在的某个字符）。然后，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://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/ http://codeforces.com/blog/entry/3107 http://codeforces.com/blog/entry/3107

我可以看到how它有效，但我不明白why。这看起来几乎就像黑魔法。我有一种非常强烈的直觉认为这项任务应该完成O(n^2)，但这里有一个算法可以做到这一点O(n)

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

例证（引自解释）：

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

所以，让我们尝试更直观......

首先，我猜测 O(n^2) 的常见直觉是这样的：对于长度为 N 的字符串，如果您被放置在字符串中的随机位置 i 且没有其他信息，则必须匹配 x (

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

让我们来看看。

首先，只要没有匹配项 (Z[i]=0)，您就会沿着字符串前进，每个字符进行一次比较，因此时间复杂度为 O(N)。 其次，当您找到匹配的范围（在索引 i 处）时，技巧是使用先前的 Z[0...i-1] 进行巧妙的推导来计算该范围内的所有 Z 值在恒定时间内, 没有其他比较在该范围内。接下来的比赛将只在范围的右侧进行。

反正我是这么理解的，希望对你有帮助。