查找字符串中重复子字符串的数量
我正在寻找一种算法,可以在单个字符串中查找重复子字符串的数量。查找字符串中重复子字符串的数量
为此,我一直在寻找一些动态编程算法,但没有找到任何帮助我的东西。我只想要一些关于如何做到这一点的教程。
比方说,我有一个字符串ABCDABCDABCD
。预计产量为3
,因为有ABCD
3次。
对于输入AAAA
,输出将是4
,因为A
重复4次。
对于输入ASDF
,输出将是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次。
你想如何指定“重复字符串”?它只是第一组字符,直到a)第一个字符被再次找到,b)该模式开始重复,或c)其他一些标准?因此,如果你的字符串是“ABBAABBA”,是2是因为“ABBA”重复两次,还是1,因为你有“ABB”后跟“AAB”? “ABCDABCE”是什么 - “ABC”是否计数(尽管重复之间有“D”?)在“ABCDABCABCDABC”中,是重复字符串“ABCD”(1)还是“ABCDABC”?
那么“AAABBAAABB” - 3(“AAA”)还是2(“AAABB”)?
如果重复字符串的结尾是第一个字母的另一个实例,这是很简单的:
通过字符串字符您的工作方式,把每一个字符到另一个变量,当您去,直到下一个字符匹配第一个。然后,给定第二个变量中子字符串的长度,检查字符串的下一位以查看它是否匹配。继续,直到它不匹配或者您击中字符串的末尾。
如果你只是想找到任何重复的长度模式,而不管第一个字符在模式中是否重复,它会变得更加复杂(但是,幸运的是,这是计算机擅长的事情)。
你需要逐个角色在另一个变量中构建一个模式,但是你还必须注意第一个字符重新出现,并且随着时间的推移开始构建第二个子字符串,以查看它是否匹配第一个。这可能应该放在数组中,因为您可能会遇到第一个字符的第三个(或更多)实例,这会触发需要跟踪另一个可能的匹配。
这并不难,但有很多需要跟踪,这是一个相当恼人的问题。你有这个特殊原因吗?
对不起,我没有完全指定我的问题,我的不好,但我得到了我需要的答案,感谢帮助 回答你的问题:我做这个的原因是为了学校项目 – mereth
不用担心,我很高兴你得到了答案。 –
它们必须是连续的吗? ABCZXABXYZAB'怎么样?可以有多个?例如:'FOO BAR BAZ FOO'应该找到'(空格)','FOO','BA'。 –