如何使用KMP失败函数确定最小长度重复子字符串？

Question

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

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

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

Answer 1

请记住，Pi[i]被定义为your_string最长的前缀，它是子字符串your_string[0 ... i]的适当后缀(而不是整个字符串)。

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

    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 (前缀函数/表)所做的事情。

现在，博客上写着：

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

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

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

Answer 2

问题

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中的以前的 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不可能存在。

Answer 3

• 假设您有一个大小为n的字符串，它看起来类似于s=x1x2x3.xn-2xn-1xn
• 假设s具有最大公共前缀/长度len后缀。
• 则周期为p= (n - len)，当且仅当n%p == 0
• 感应：
  • 表示前缀= s1...len，后缀= sp+1...n
  • 然后我们有前缀1.p ==后缀1.p == sp+1...2p
  • 自从sp+1...2p == prefixp+1...2p如此邮政1.p == postfixp+1...2p
  • 递归postfixp+1...2p == s2p+1...3p == prefix2p+1...3p
  • ..。