查找字符串中重复子串的数量

Question

我正在寻找一种算法，可以找到单个字符串中重复子字符串的数量。

为此，我一直在寻找一些动态编程算法，但没有找到任何对我有帮助的算法。我只是想要一些关于如何执行此操作的教程。

假设我有一个字符串ABCDABCDABCD。预期输出为3，因为有ABCD3 次。

对于输入AAAA，输出将为4，因为A重复了 4 次。

对于输入ASDF，输出将为1，因为每个单独的字符仅重复 1 次。

我希望有人能指出我正确的方向。谢谢。

Answer 1

我采取以下假设：

• 重复的子串必须是连续的。也就是说，在以下情况下ABCDABC，ABC就不能算作重复子，但它会在以下情况下ABCABC。
• 重复的子字符串必须是非重叠的。也就是说，在 的情况下ABCABC，ABC不会算作重复子串。
• 在多个可能的答案的情况下，我们想要具有最大值的答案。也就是说，在 的情况下AAAA，答案应该是4(a是子串) 而不是2(aa是子串)。

在这些假设下，算法如下：

• 让输入字符串表示为inputString。
• 计算输入字符串的KMP 失效函数数组。让这个数组表示为failure[]。该操作相对于字符串的长度具有线性时间复杂度。因此，根据定义，failure[i]表示子串的最长专有前缀的长度inputString[0....i]，它也是同一子串的专有后缀。
• 让len = inputString.length - failure.lastIndexValue. 此时，我们知道如果有任何重复的字符串，那么它必须是这个长度len。但我们需要检查一下；首先，只需检查是否len完全分开inputString.length（即inputString.length % len == 0）。如果是，则检查每个连续（非重叠）的len字符子串是否相同；该操作相对于输入字符串的长度再次具有线性时间复杂度。
• 如果结果证明每个连续的非重叠子串都是相同的，那么答案将是 = inputString.length/ len。否则，答案很简单inputString.length，因为不存在这样的重复子串。

总时间复杂度为O(n)，其中n是输入字符串中的字符数。

此处给出了用于计算 KMP 故障数组的示例代码。

例如，

让输入字符串为abcaabcaabca。

它的 KMP 故障数组将是 - [0, 0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 8]。

所以，我们的len= (12 - 8) = 4。

并且每个连续的非重叠长度的子串4都是相同的（abca）。
因此答案是12/4= 3。即abca反复重复3次。