如何使用 KMP 失败函数确定最小长度重复子串？
How to use KMP failure function to determine minimum length repeated substring?
我想解决 UVA 10298 -"Power Strings" problem using KMP algorithm. In this 博客显示了如何使用失败函数计算最小长度重复子串的技巧。技巧如下：
- 计算给定字符串的前缀-后缀 table
pi[ ]。
- 令
len为字符串长度，last_in_pi为存储在pi table. 的最后一个索引处的值
- 检查
len % (len - last_in_pi) == 0是否正确。如果为真则最小长度重复子串的长度为(len - last_in_pi)，否则为给定字符串的长度
我了解什么是故障函数以及如何使用它来查找文本中的模式，但我很难理解该技术正确性的证明。
请记住，Pi[i] 被定义为 your_string 的最长前缀（长度），它是子字符串 your_string[0 ... i] 的适当后缀（因此不是整个字符串）。
您链接到的博客 post 上有一个示例：
0 1 2 3 4 5
S : a b a b a b
Pi: 0 0 1 2 3 4
我们有：
a b a
a b a b
等我希望这能说明 Pi（前缀函数/table）的作用。
现在，博客说：
The last value of prefix table = 4..
Now If it is a repeated string than , It’s minimal length would be 2. (6(string length) – 4) , Now
所以你必须检查 len % (len - last_in_pi) == 0。如果是，那么len - last_in_pi就是最短的重复串（句号串）的长度。
这是可行的，因为如果您以任何方式旋转具有 len(period) 个位置的字符串，它都会匹配自身。 len - last_in_pi 告诉您需要旋转多少。
问题
S（长度Ls）是给定的字符串。 M（长度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 中的 previous Ly 个字符追加到它后面。这不会超过字符串长度，因为 (Ly < Ls - Lm)。新的后缀是 (n + 1)*Y + Z.
考虑 M 前缀。现在将原始字符串 S 中的 next 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不可能存在。
- 假设你有一个大小为 n 的字符串 s，它看起来像 s = x1x2x3...x[n-2]x[n-1]x[n]
- 假设 s 的最大公共 prefix/suffix 长度为 len
- 那么它的周期是 p = (n - len)，当且仅当 n % p == 0
- 归纳：
- 表示前缀 = s[1...len]，后缀 = s[p+1...n]
- 然后我们有前缀[1...p] == 后缀[1...p] == s[p+1...2p]
- 因为 s[p+1...2p] == prefix[p+1...2p] 所以 postfix[1...p] == postfix[p+1...2p]
- 递归后缀[p+1...2p] == s[2p+1...3p] == 前缀[2p+1...3p]
- ...
我想解决 UVA 10298 -"Power Strings" problem using KMP algorithm. In this 博客显示了如何使用失败函数计算最小长度重复子串的技巧。技巧如下：
- 计算给定字符串的前缀-后缀 table
pi[ ]。 - 令
len为字符串长度，last_in_pi为存储在pitable. 的最后一个索引处的值
- 检查
len % (len - last_in_pi) == 0是否正确。如果为真则最小长度重复子串的长度为(len - last_in_pi)，否则为给定字符串的长度
我了解什么是故障函数以及如何使用它来查找文本中的模式，但我很难理解该技术正确性的证明。
请记住，Pi[i] 被定义为 your_string 的最长前缀（长度），它是子字符串 your_string[0 ... i] 的适当后缀（因此不是整个字符串）。
您链接到的博客 post 上有一个示例：
0 1 2 3 4 5
S : a b a b a b
Pi: 0 0 1 2 3 4
我们有：
a b a
a b a b
等我希望这能说明 Pi（前缀函数/table）的作用。
现在，博客说：
The last value of prefix table = 4.. Now If it is a repeated string than , It’s minimal length would be 2. (6(string length) – 4) , Now
所以你必须检查 len % (len - last_in_pi) == 0。如果是，那么len - last_in_pi就是最短的重复串（句号串）的长度。
这是可行的，因为如果您以任何方式旋转具有 len(period) 个位置的字符串，它都会匹配自身。 len - last_in_pi 告诉您需要旋转多少。
问题
S（长度Ls）是给定的字符串。 M（长度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 中的 previous Ly 个字符追加到它后面。这不会超过字符串长度，因为 (Ly < Ls - Lm)。新的后缀是 (n + 1)*Y + Z.
考虑 M 前缀。现在将原始字符串 S 中的 next 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不可能存在。
- 假设你有一个大小为 n 的字符串 s，它看起来像 s = x1x2x3...x[n-2]x[n-1]x[n]
- 假设 s 的最大公共 prefix/suffix 长度为 len
- 那么它的周期是 p = (n - len)，当且仅当 n % p == 0
- 归纳：
- 表示前缀 = s[1...len]，后缀 = s[p+1...n]
- 然后我们有前缀[1...p] == 后缀[1...p] == s[p+1...2p]
- 因为 s[p+1...2p] == prefix[p+1...2p] 所以 postfix[1...p] == postfix[p+1...2p]
- 递归后缀[p+1...2p] == s[2p+1...3p] == 前缀[2p+1...3p]
- ...