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)
中完成，我也不觉得它完全直观，所以我认为我有资格回答。否则，我只能说你不明白，因为你是个白痴，当然这不是你所希望的答案：-）
一个恰当的例子（引用解释）：
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值，而不在该范围内进行其他比较。接下来的比赛将只在场地右侧进行。
我就是这么理解的，希望这能有所帮助。
我想对这个算法有更深入的了解，所以我发现了这个问题。
起初我不理解codeforces的帖子，但后来我发现它足够好理解，我注意到这个帖子并不完全准确，而且它省略了思考过程中的一些步骤，让它有点混乱。
让我试着纠正那篇文章中的错误，并澄清一些我认为可能有助于人们将点与线联系起来的步骤。在这个过程中，我希望我们能从原作者那里学到一些直觉。在解释中，我将把一些引用的代码块和我自己的笔记混合在一起，这样我们就可以把原始帖子放在我们讨论的附近。
Z算法开始时为：
当我们迭代字符串中的字母时（索引i从1到n-1） ，我们保持区间[L，R] 其是具有最大R的区间，使得1≤L≤我≤R和S[L…R]是前缀子串（如果不存在这样的区间，就让L=R= -1） 。对于我=1，我们可以通过比较S[0]…]和S[1…]来简单地计算L和R。此外，在此过程中我们还得到了Z1。
这很简单明了。
现在假设我们有正确的区间[L，R] 对于我-1和i之前的所有Z值-1.我们将计算Z[i]和新的[L，R] 通过以下步骤：
- 如果i>R、 则不存在在i之前开始并且在i处或之后结束的S的前缀子串。如果存在这样的子串，[L，R] 将是该子字符串的间隔，而不是其当前值。因此，我们"重置"并计算一个新的[L，R] 通过将S[0]…]与S[i…]进行比较，同时得到Z[i]（Z[i]=R-L+1）
要点中的粗体部分可能会令人困惑，但如果你读两遍，它实际上只是在重复R的定义。
- 否则，我≤R、 因此电流[L，R] 至少延伸到i。设k=我-L.我们知道Z[i]≥min（Z[k]，R-我+1） 因为S[i…]与S[k…]匹配至少R-我+1个字符（它们在[L，R] 我们知道是前缀子串的间隔）。现在我们还有几个案例需要考虑
粗体部分并不完全准确，因为R-我+1可以大于Z[k]，在这种情况下Z[i]将是Z[k]。
现在让我们关注关键：Z[i]≥min（Z[k]，R-我+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<R-i+1。点是，S[k…k+x]＝=S[i…i+x]，所以当Z[k]<R-i+1
这些是我在开头提到的缺失点，它们解释了第二个和第三个要点，部分解释了最后一个要点。当我读到codeforces的帖子时，这并不简单。对我来说，这是这个算法中最重要的部分。
对于最后一个项目符号点，如果Z[k]≥R-我+1，我们将刷新[L，R]，使用i作为新的L，并将R扩展到更大的R'。
在整个过程中，Z算法只使用每个字符一次进行比较，因此时间复杂度为O（n）。
正如Ilya所回答的，这种算法的直觉是仔细地重复使用我们迄今为止收集的每一条信息。我只是用另一种方式解释了。希望能有所帮助。