1

我想使用 KMP 算法解决UVA 10298 -“Power Strings”问题。在这篇博客中，展示了如何使用失效函数来计算最小长度重复子串的技术。该技术如下：

  1. pi[ ]计算给定字符串的前缀-后缀表。
  2. 令len为字符串长度，并last_in_pi为存储在pi表的最后一个索引处的值。
  3. 检查len % (len - last_in_pi) == 0是真是假。如果为真，则最小长度重复子串的长度为(len - last_in_pi)，否则为给定字符串的长度。

我了解什么是失败函数以及它如何用于在文本中查找模式，但我很难理解这种技术的正确性证明。

4

3 回答 3

5

请记住，它Pi[i]被定义为（的）最长前缀，your_string它是 substring 的正确后缀（所以不是整个字符串）your_string[0 ... i]。

您链接到的博客文章中有一个示例：

    0 1 2 3 4 5
S : a b a b a b
Pi: 0 0 1 2 3 4

我们在哪里：

啊啊啊_

抗体 _

等等。我希望这能清楚地说明Pi（前缀函数/表）的作用。

现在，博客说：

前缀表的最后一个值 = 4.. 现在如果它是一个重复的字符串而不是 ，它的最小长度将是 2. (6(string length) – 4) , 现在

所以你必须检查是否len % (len - last_in_pi) == 0. 如果是，len - last_in_pi则为最短重复字符串（句点字符串）的长度。

这是有效的，因为如果您以任一方式旋转具有len(period)位置的字符串，它将匹配自身。len - last_in_pi告诉您需要旋转多少。

于 2015-07-23T11:23:10.460 回答
1

问题

S（长度Ls）是给定的字符串。M(of length Lm) 是 的最大真后缀S，也是 的前缀S。我们要证明Ls - Lm的是最短周期的长度S。

矛盾证明

假设有一个周期Y的长度Ly < Ls - Lm（即，它比上述技术给出的周期短）。

需要注意的一个重要属性是它M是一个适当的前缀，Y反之亦然，具体取决于它们的长度。我们可以将其表示为M = n*Y + Z，其中n >= 0和Z是附加部分 和Lz < Ly。Z形成 的前缀Y，因为Y重复。让Y = Z + W.

考虑M后缀。将原始字符串 S 中的前 几个字符附加到它。Ly这不会超过字符串长度，因为 ( Ly < Ls - Lm)。新的后缀是(n + 1)*Y + Z.

考虑M前缀。现在将原始字符串 S 中的下一个 字符附加到它。Ly这里的新前缀是

M + (next Ly characters from S)
- > n*Y + Z + (Ly characters)  
- > n*Y + Z + (Ly - Lz characters) + (Lz characters)  
- > n*Y + (Z + W) + (Z)  
{The `Ly - Lz` characters should be `W` because `Z` and these together form `Y`; The last Lz characters are actually the the first Lz characters of Y which is nothing but Z}  

- > (n + 1)*Y + Z

现在我们有了一个适当的 S 后缀，它也是一个前缀并且大于M。但是我们开始说M最长的正确后缀也是前缀。所以这是一个矛盾，意味着这样的Y不可能存在。

于 2018-09-26T04:33:47.977 回答
0
  • 假设你有一个大小为 n 的字符串 s，它看起来像 s = x1x2x3...x[n-2]x[n-1]x[n]
  • 假设 s 的最大公共前缀/后缀长度为 len
  • 那么它的周期是 p = (n - len), iff n % p == 0
  • 就职：
    • 表示前缀 = s[1...len]，后缀 = s[p+1...n]
    • 然后我们有前缀[1...p] == 后缀[1...p] == s[p+1...2p]
    • 由于 s[p+1...2p] == 前缀[p+1...2p] 所以后缀[1...p] == 后缀[p+1...2p]
    • 递归后缀[p+1...2p] == s[2p+1...3p] == 前缀[2p+1...3p]
    • ...
于 2020-10-10T16:56:32.353 回答