我试图在长度为 n 的字符串中找到等于后缀及其长度的前缀数。它们可以重叠,例如,如果字符串是“abacaba”,则 ans 是 {1, 3, 7} 长度为 1 (a) 的前缀,3 是“aba”和整个字符串。前缀“a”等于后缀“a”。前缀“aba”等于后缀“aba”。整个字符串等于后缀。如果字符串是“aaaaa”,那么答案是 {1, 2, 3, 4, 5}。“a”、“aa”、“aaa”、“aaaa”、“aaaaa”。
我只能在 O(n2) 中得到,其中我们取每个前缀并与相同长度的后缀进行比较。但是有没有更好的算法来解决这个问题?提前致谢
我的方法需要 O(N) 时间来预处理字符串,然后 O(|ans array|) 来计算答案。
预处理基本上是 KMP 故障表构建部分,在除最后一个字符之外的整个字符串上。("abacab"
在你的例子中)。在之前返回的表中,给定字符串(即5
或'b'
)中最后一个索引的值将为 2。这意味着与以 'b' 结尾的 AND 匹配的最大前缀为 2。现在,如果您的最后一个字符与前缀 ( 'a'
) 的第三个字符匹配,则您的后缀等于前缀。( "aba"
)
KMP 就停在那里。但是你想要所有的比赛。因此,不是以最后一个字符(2 in 'b'
)结尾的最大匹配,您需要找到前缀以“b”结尾的所有匹配。因此,您继续进入 KMP 的内部循环,并且像上面一样,如果下一个字符等于我们的最后一个字符,则检查以“b”(可以为零)结尾的当前匹配量。
def build_table(pat):
table = [0]*len(pat)
p = 0
for i in range(1,len(pat)):
while p>0 and pat[p]!=pat[i]: #KMP's loop i was talking about
p = table[p-1]
if pat[p]==pat[i]:
table[i] = p+1
p+=1
return table
pat = "abracadabab"
table = build_table(pat[:-1]) #build table for "abracadaba", i.e except last
ans = [] #to store answers
p = len(pat)-1 #last index of table building string i.e 5 or 'b'
while p>0: #the main loop
p = table[p-1]
print(p)
if pat[p]==pat[-1]:
ans.append(p+1)
print(ans)
对于"abacab"
打印[1,3]
,因为"abracadabra"
它是[1,4]
. 将整个长度视为特殊情况。
(请注意我的while
循环和 KMP 循环之间的相似性。如果您仍然感到困惑,我强烈建议您彻底阅读/理解 KMP。对此有一个整体的了解很容易,但深入理解对于回答这样的问题确实很难且至关重要.)
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句