这是来自这个帖子(查找最短的整个重复子字符串)的一个新的讨论,因为它是全新的代码,所以我在这里作为一个新线程发布。
发布新线程的主要举措是,RobAu发布了一个更聪明的想法,没有实现,我实现了这些想法,并简单地证明了这些想法是正确的。张贴我的代码和简单的证明在这里征求意见。
问题是,
我正在解决一个问题,以找到给定字符串的完全重复的最短子字符串,如果没有匹配,则返回整个原始字符串。
catcatcat => cat
catcatcatdog=>catcatcatdog
aaaaaa = > a算法的主要思想,
尝试将第一个最短的重复候选作为原始字符串的第一个字符,如果没有匹配,则将整个不匹配字符串视为下一个候选字符。
我有一个简单的证明为什么if there is no match, treat the whole non-matched string as next candidate是正确的,
N,并且在当前的比较中不能满足,以前的匹配长度是N*k (前一个候选人匹配k时间)。N+x (1<x<N),并且该候选可以匹配以前匹配的字符串的p时间。然后,N*k = (N+x)*p,换句话说,N*k/(N+x) = p,因为N/(N+x)不是整数,但是k和p都是整数,所以不能满足。(同时,我们知道如果N长度字符串不匹配,2N、3N等不匹配,这就是为什么在前面的分析中选择x作为1和N之间的值的原因。)def check_shortest(original_string):
current_candidate = original_string[0]
j = 0
for i in range(len(original_string)):
if original_string[i] == current_candidate[j]:
j+=1
if j == len(current_candidate):
j = 0
else:
current_candidate= original_string[:i+1]
return current_candidate if j == 0 else original_string
if __name__ == "__main__":
print check_shortest('catcatcat') #cat
print check_shortest('catcatcatdog') #catcatcatdog
print check_shortest('aaaaaa') #a
print check_shortest('aba') # aba发布于 2016-10-23 04:48:46
你目前写道:
for i in range(len(original_string)):考虑使用enumerate:
for i, char in enumerate(original_string):
if char == current_candidate[j]:enumerate允许您以一种很好的方式引用当前对象,同时还可以为您提供项所属的索引。
发布于 2016-10-23 12:33:22
不太成功地试图修复罗布/林马的方法,而且不再简单了:
# Find "period" of a string:
# prefixes, grown as needed and warranted become candidates
def shortestCover(original):
"""return the shortest substring of the argument
that equals it when repeated an integral number of times.
BROKEN(incomplete): fails for 'ababccabababccabababccab'
(repetitions of more than just one char
at start _and_ end at special positions)
"""
print "shortestCover BROKEN: fails for 'ababccabababccabababccab'"
# length of prefix of original that might cover it if repeated
candidate = i = 1
oLen = len(original) # define halfLen?
# print original, oLen
prefix = 0
while (i < oLen):
# print i, candidate, prefix
# no need for modulus:
# the immediately preceding occurrence of
# the candidate pattern is as good as the first
if original[i] == original[i - candidate]:
i += 1
else:
if oLen // 2 < i: return original
# part or all of prefix has unsuccessfully been assumed
# to be the start of the next occurrence:
# candidate may need to be as far back from i as prefix,
# but must grow
# (without re-scanning that part,
# this does _not_ raise WC run-time to O(n^3/2) )
if (i <= candidate+prefix):
candidate = max(candidate, i-prefix)+1
# comparisons would be redundant upto&including i
while (0 != oLen % candidate
and candidate <= i):
candidate += 1
else:
candidate = i + 1
# if prefix isn't set yet,
# original starts with i occurrences of its 1st char
if prefix == 0:
prefix = i
# allow divisors of original length as candidates, only
while (0 != oLen % candidate):
candidate += 1
if oLen // 2 < candidate: return original
# this may skip characters that never get nor need to be
# "on the right side of a comparison for equality"
i = candidate if i < candidate else i+1;
return original[:candidate]
import re
if __name__ == "__main__":
for o in (#'',
'abababab', 'aaaaaa', # not a prime length
'ababa', 'abaaba', 'abaaaba',
'aabaaba', 'aabaaaba', 'aabaaaaba',
'aaaaccaaaaaaccaaaaaaccaa',
'ababbbabababbbabababbbab',
'ababbbababbbababbbababbb',
'ababccabababccabababccab'):
print re.match(r'^(.+?)\1*, o).group(1)
print shortestCover(o)https://codereview.stackexchange.com/questions/144973
复制相似问题