Z 函数和独特的子串：破烂的算法随处可见？
Z-Function and unique substrings: broken algorithm parroted everywhere?
我不是一个超级数学迷，所以我可能很容易遗漏一些东西，但让我们从 https://cp-algorithms.com/string/z-function.html 中获取算法并尝试将其应用于字符串 baz。这个字符串肯定有子串集'b','a','z','ba','az','baz'.
让我们看看 z 函数是如何工作的（至少我是如何理解它的）：
- 我们取一个空字符串并向其添加 'b'。根据算法 z[0] = 0 的定义，因为它未定义大小 1;
- 我们取 'b' 并向其添加 'a'，反转字符串，我们有 'ab'... 现在我们计算 z 函数... 它产生 {0 , 0}。第一个元素是预期的“未定义”，第二个元素应定义为：
i-th element is equal to the greatest number of characters starting from the position i that coincide with the first characters of s.
所以，在 i = 1 处，我们有 'b'，我们的字符串以 a 开头，'b' 与 'a' 不一致，所以当然是 z[i=1]= 0。这将在整个单词中重复。最后，我们留下了全零的 z 数组，尽管该字符串有 6 个子字符串，但它什么也没告诉我们。
我错过了什么吗？有大量网站推荐 count of distinct substrings 的 z 函数，但它...不起作用？我在这里误解了 distinct 的意思吗？
当你在字符串S[=44=的开头添加一个字符x时，S[的所有子串 仍然是 xS 的子串，但是你得到了多少 new 子串？
- 新的子串都是xS的前缀。这些有长度(xS)，但是
其中- max(Z(xS))已经是S的子串，所以
- 你得到长度(xS) - max(Z(xS)) 新的
因此，给定一个字符串 S，只需将所有长度 (P) - max(Z(P)) 相加即可S.
的每个后缀 P
您的测试用例 baz 有 3 个后缀：z、az 和 baz。所有字母都是不同的，因此它们的 Z 函数处处为零。结果是不同子串的数量正好是后缀长度的总和：3 + 2 + 1 = 6.
尝试baa：Z函数中唯一的non-zero是Z('aa')[1] = 1，所以唯一子串的个数是3 + 2 - 1 + 1 = 5.
请注意，您链接到的文章提到这是一个 O(n2) 算法。这是正确的，尽管它的开销很低。通过构建后缀树可以在 O(n) 时间内完成此操作，但这相当复杂。
我不是一个超级数学迷，所以我可能很容易遗漏一些东西，但让我们从 https://cp-algorithms.com/string/z-function.html 中获取算法并尝试将其应用于字符串 baz。这个字符串肯定有子串集'b','a','z','ba','az','baz'.
让我们看看 z 函数是如何工作的（至少我是如何理解它的）：
- 我们取一个空字符串并向其添加 'b'。根据算法 z[0] = 0 的定义，因为它未定义大小 1;
- 我们取 'b' 并向其添加 'a'，反转字符串，我们有 'ab'... 现在我们计算 z 函数... 它产生 {0 , 0}。第一个元素是预期的“未定义”，第二个元素应定义为：
i-th element is equal to the greatest number of characters starting from the position i that coincide with the first characters of s.
所以，在 i = 1 处，我们有 'b'，我们的字符串以 a 开头，'b' 与 'a' 不一致，所以当然是 z[i=1]= 0。这将在整个单词中重复。最后，我们留下了全零的 z 数组，尽管该字符串有 6 个子字符串，但它什么也没告诉我们。
我错过了什么吗？有大量网站推荐 count of distinct substrings 的 z 函数，但它...不起作用？我在这里误解了 distinct 的意思吗？
当你在字符串S[=44=的开头添加一个字符x时，S[的所有子串 仍然是 xS 的子串，但是你得到了多少 new 子串？
- 新的子串都是xS的前缀。这些有长度(xS)，但是 其中
- max(Z(xS))已经是S的子串，所以
- 你得到长度(xS) - max(Z(xS)) 新的
因此，给定一个字符串 S，只需将所有长度 (P) - max(Z(P)) 相加即可S.
的每个后缀 P您的测试用例 baz 有 3 个后缀：z、az 和 baz。所有字母都是不同的，因此它们的 Z 函数处处为零。结果是不同子串的数量正好是后缀长度的总和：3 + 2 + 1 = 6.
尝试baa：Z函数中唯一的non-zero是Z('aa')[1] = 1，所以唯一子串的个数是3 + 2 - 1 + 1 = 5.
请注意，您链接到的文章提到这是一个 O(n2) 算法。这是正确的，尽管它的开销很低。通过构建后缀树可以在 O(n) 时间内完成此操作，但这相当复杂。