python - 使用python查找字符串中特定长度的重复项

Question

我正在尝试使用 regex用于在给定字符串(30 个字符)内查找非重叠重复(重复的子字符串)的模块，具有以下要求:

1. 我只对 6-15 个字符长的非重叠重复感兴趣。
2. 允许 1 个不匹配
3. 返回每场比赛的位置

我想到的一种方法是，对于每个可能的重复长度，让 python 循环遍历 30 个字符的字符串输入。例如，

string = "ATAGATATATGGCCCGGCCCATAGATATAT" #input

#for 6char repeats, first one in loop would be for the following event:

text = "ATAGAT"
text2 ="(" + text + ")"+ "{e<=1}" #this is to allow 1 mismatch later in regex

string2="ATATGGCCCGGCCCATAGATATAT" #string after excluding text

for x in regex.finditer(text2,string2,overlapped=True):
    print x.span()

#then still for 6char repeats, I will move on to text = "TAGATA"...
#after 6char, loop again for 7char...

此特定字符串 =“ATAGATATATGGCCCGGCCCATAGATATAT”应该有两个输出。 1、粗体两个“ATAGATATAT”+1不匹配:“ATAGATATATG”&“CATAGATATAT”，位置索引返回为(0,10)&(19, 29)； 2.“TGGCCC”和“GGCCCA”(需要添加一个不匹配至少6个字符)，索引为(9,14)&(15,20)。数字可以位于列表或表格中。

很抱歉我没有包含真正的循环，但我希望这个想法很清楚...正如您所看到的，这是一种效率非常低的方法，更不用说它会产生冗余 ---例如10 个字符重复将被计算多次，因为它适合 9、8、7 和 6 个字符重复循环。此外，我有很多这样的 30 个字符的字符串需要使用，所以我很感激您对一些更简洁的方法的建议。

非常感谢:)

Answer 1

我会尝试使用简单的算法而不是正则表达式(在这种情况下这很令人困惑)；

s = "ATAGATATATGGCCCGGCCCATAGATATAT"

def fuzzy_compare(s1, s2):
    # sanity check
    if len(s1) != len(s2):
        return False

    diffs = 0
    for a, b in zip(s1, s2):
        if a != b:
            diffs += 1

        if diffs > 1:
            return False        

    return True

slen = len(s) # 30
for l in range(6, 16):
  i = 0
  while (i + l * 2) <= slen:
    sub1 = s[i:i+l]
    for j in range(i+l, slen - l):
        sub2 = s[j:j+l]
        if fuzzy_compare(sub1, sub2):
            # checking if this could be partial
            partial = False
            if i + l < j and j + l < slen:
                extsub1 = s[i:i+l+1]
                extsub2 = s[j:j+l+1]
                # if it is partial, we'll get it later in the main loop
                if fuzzy_compare(extsub1, extsub2):
                   partial = True

            if not partial: 
                print (i, i+l), (j, j+l)

    i += 1

这是初稿，所以请随意尝试。它似乎也很笨重并且不是最佳的，但是尝试先运行它 - 它可能就足够了。