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

Question

我正在尝试使用 regex 模块在给定字符串（30 个字符）中查找非重叠重复（重复的子字符串），并满足以下要求：

我只对长度为 6-15 个字符的非重叠重复感兴趣。
允许 1 次不匹配
return每场比赛的位置

我想到的一种方法是，对于每个可能的重复长度，让 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" with position index returned as (0,10)&(19, 29); 2. "TGGCCC" & "GGCCCA"（需要添加一个不匹配至少为 6 个字符），索引为 (9,14)&(15,20)。数字可以在列表中或 table.

很抱歉我没有包含一个真正的循环，但我希望这个想法很清楚...如您所见，这是一种非常低效的方法，更不用说它会产生冗余 - -- 例如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

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

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

Find repeats with certain length within a string using python

python

regex

loops

mismatch