我不是一个巨大的数学书呆子，所以我可能很容易遗漏一些东西，但是让我们从https://cp-algorithms.com/string/z-function.html中获取算法并尝试将其应用于 string baz。这个字符串肯定有一个子字符串集'b'，'a'，'z'，'ba'，'az'，'baz'。
让我们看看 z 函数是如何工作的（至少我是怎么理解的）：
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 个子字符串，但它并没有告诉我们任何信息。
我错过了什么吗？有很多网站推荐 z 功能，count of distinct substrings但它......不起作用？我是不是误解了distinct这里的意思？
当您在字符串 S 的开头添加一个字符x时，S的所有子字符串仍然是xS的子字符串，但是您得到了多少个新子字符串？
因此，给定一个字符串 S，只需将 S的每个后缀P的所有长度 ( P ) - max(Z( P )) 相加即可。
您的测试用例baz有 3 个后缀：z、az和baz. 所有字母都是不同的，因此它们的 Z 函数处处为零。结果是不同子串的数量只是后缀长度的总和：3 + 2 + 1 = 6。
尝试baa：Z 函数中唯一的非零是 Z('aa')[1] = 1，因此唯一子串的数量是 3 + 2 - 1 + 1 = 5。
请注意，您链接到的文章提到这是一个 O(n 2 ) 算法。这是正确的，尽管它的开销很低。通过构建后缀树可以在 O(n) 时间内完成此操作，但这非常复杂。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句