1

我的问题类似于找到最长的重复非重叠子字符串，但以这种方式。例如，我的输入数组是0,0,0,1,2,1,1,2,1,1,2,1,2,0,0

此输入中最长的重复且不重叠的子字符串121的计数为3 Now，121从输入数组中删除出现的 并将其替换为-1。

我的输入现在变为：0,0,0,-1,-1,-1,2,0,0 现在再次找到相同的子字符串。

注意：答案中不应包含-1。因此，下一个最长的非重叠和重复子串是00count as 2。

从输入中删除出现的 0,0，然后变为：0,-1,-1,-1,2,-1 现在唯一出现的是长度为 1 的 0 和 2。所以，我们在这里停止。

我只能想到 O(n 3 ) 的蛮力。也尝试过考虑后缀树，但不知道如何在其中包含非重叠条件。

我非常天真的实现：

因为我希望我的子字符串的计数至少为 2，所以它的最大长度可以为 N/2（N 是输入数组的大小）

for len = N/2 to 1:
    // find all sub-strings of length as "len" in the input sequence
    for i=0 to N-len+1
        // the sub-string is s[i... (i+len)]
        // find non-overlapping count of this sub-string in the input sequence using KMP
        int count = find_Count();
        // take the substring with maximum count, let it be "r"
    end
    modify the array to place replace non-overlapping occurrences of "r" with -1
end

如上所示，复杂度为 O(N 3 )。

任何最佳解决方案、提示或解释都会有所帮助。

谢谢

4

0 回答 0