查找字符串中重複子字符串的數量

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」）？

如果重複字符串的結尾是第一個字母的另一個實例，這是很簡單的：

通過字符串字符您的工作方式，把每一個字符到另一個變量，當您去，直到下一個字符匹配第一個。然後，給定第二個變量中子字符串的長度，檢查字符串的下一位以查看它是否匹配。繼續，直到它不匹配或者您擊中字符串的末尾。

如果你只是想找到任何重複的長度模式，而不管第一個字符在模式中是否重複，它會變得更加複雜（但是，幸運的是，這是計算機擅長的事情）。

你需要逐個角色在另一個變量中構建一個模式，但是你還必須注意第一個字符重新出現，並且隨着時間的推移開始構建第二個子字符串，以查看它是否匹配第一個。這可能應該放在數組中，因爲您可能會遇到第一個字符的第三個（或更多）實例，這會觸發需要跟蹤另一個可能的匹配。

這並不難，但有很多需要跟蹤，這是一個相當惱人的問題。你有這個特殊原因嗎？