首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >查找最短的整个重复子字符串(第3部分)

问查找最短的整个重复子字符串(第3部分)
EN

Code Review用户
提问于 2016-10-23 02:07:19
回答 2查看 697关注 0票数 2

这是来自这个帖子(查找最短的整个重复子字符串)的一个新的讨论,因为它是全新的代码,所以我在这里作为一个新线程发布。

发布新线程的主要举措是,RobAu发布了一个更聪明的想法,没有实现,我实现了这些想法,并简单地证明了这些想法是正确的。张贴我的代码和简单的证明在这里征求意见。

问题是,

我正在解决一个问题,以找到给定字符串的完全重复的最短子字符串,如果没有匹配,则返回整个原始字符串。

输入输出示例

代码语言:javascript
复制
catcatcat => cat
catcatcatdog=>catcatcatdog
aaaaaa = > a

算法的主要思想,

尝试将第一个最短的重复候选作为原始字符串的第一个字符,如果没有匹配,则将整个不匹配字符串视为下一个候选字符。

我有一个简单的证明为什么if there is no match, treat the whole non-matched string as next candidate是正确的,

  1. 假设前面的候选长度是N,并且在当前的比较中不能满足,以前的匹配长度是N*k (前一个候选人匹配k时间)。
  2. 假设还有另一个满意的候选项,其长度为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之间的值的原因。)
  3. 因此,我们必须将整个错误匹配的字符串视为下一个重复字符串候选项。

我的代码

代码语言:javascript
复制
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
EN

回答 2

Code Review用户

发布于 2016-10-23 04:48:46

你目前写道:

代码语言:javascript
复制
for i in range(len(original_string)):

考虑使用enumerate:

代码语言:javascript
复制
for i, char in enumerate(original_string):
    if char == current_candidate[j]:

enumerate允许您以一种很好的方式引用当前对象,同时还可以为您提供项所属的索引。

票数 1
EN

Code Review用户

发布于 2016-10-23 12:33:22

  • 使用文档字符串
  • 评论
  • 用说的,但简洁的名字
  • 尽量保持简单
  • (测试“第一”:在执行一个过程时,要有一个测试过程,以保持对它确实解决问题的信心)

不太成功地试图修复罗布/林马的方法,而且不再简单了:

代码语言:javascript
复制
# 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)
票数 1
EN
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://codereview.stackexchange.com/questions/144973

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档