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

Question

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

为此，我一直在寻找一些动态编程算法，但没有找到任何帮助我的东西。我只想要一些关于如何做到这一点的教程。

比方说，我有一个字符串ABCDABCDABCD。预计产量为3，因为有ABCD 3次。

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

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

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

Answer 1

我采取以下假设：

• 的重复子必须是连续的。也就是说，在ABCDABC的情况下，ABC不会被视为重复的子字符串，但它会在ABCABC的情况下。
• 重复的子串必须是非整数。也就是说，在ABCABC的情况下，ABC不会被视为重复子字符串。
• 如果有多个可能的答案，我们需要最大值的答案。也就是说，在AAAA的情况下，答案应该是4（a是子字符串）而不是2（aa是子字符串）。

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

• 让输入字符串被表示为inputString。
• 计算输入字符串的KMP failure function数组。让这个数组表示为failure[]。如果线性时间复杂度相对于字符串的长度，此操作。因此，根据定义，failure[i]表示子字符串inputString[0....i]的最长正确前缀的长度，其也是相同子字符串的正确后缀。
• 让len = inputString.length - failure.lastIndexValue。此时，我们知道如果有任何重复字符串，则它必须具有这个长度len。但我们需要检查一下;首先，检查len是否完全除以inputString.length（即inputString.length % len == 0）。如果是，则检查每个连续（非重叠）字符的子字符串是否相同;这个操作对于输入串的长度来说又是线性的时间复杂度。
• 如果事实证明每个连续的非重叠子串是相同的，那么答案将是= inputString.length/len。否则，答案只是inputString.length，因为不存在这样的重复子字符串。

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

用于计算KMP故障数组的示例代码为here。

---

例如，

让输入字符串是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次。

Answer 2

你想如何指定“重复字符串”？它只是第一组字符，直到a）第一个字符被再次找到，b）该模式开始重复，或c）其他一些标准？因此，如果你的字符串是“ABBAABBA”，是2是因为“ABBA”重复两次，还是1，因为你有“ABB”后跟“AAB”？ “ABCDABCE”是什么 - “ABC”是否计数（尽管重复之间有“D”？）在“ABCDABCABCDABC”中，是重复字符串“ABCD”（1）还是“ABCDABC”？

那么“AAABBAAABB” - 3（“AAA”）还是2（“AAABB”）？

如果重复字符串的结尾是第一个字母的另一个实例，这是很简单的：

通过字符串字符您的工作方式，把每一个字符到另一个变量，当您去，直到下一个字符匹配第一个。然后，给定第二个变量中子字符串的长度，检查字符串的下一位以查看它是否匹配。继续，直到它不匹配或者您击中字符串的末尾。

如果你只是想找到任何重复的长度模式，而不管第一个字符在模式中是否重复，它会变得更加复杂（但是，幸运的是，这是计算机擅长的事情）。

你需要逐个角色在另一个变量中构建一个模式，但是你还必须注意第一个字符重新出现，并且随着时间的推移开始构建第二个子字符串，以查看它是否匹配第一个。这可能应该放在数组中，因为您可能会遇到第一个字符的第三个（或更多）实例，这会触发需要跟踪另一个可能的匹配。

这并不难，但有很多需要跟踪，这是一个相当恼人的问题。你有这个特殊原因吗？