字符串regex两个不匹配的Python

Question

如何扩展下面的代码以允许我探索所有子字符串与父字符串不匹配或不匹配的所有实例？在

子字符串：SSQP

要匹配的字符串：SSPQQQQPSSSSQQQSSQPSPSQSSQPSSQPPSSSSQPSPSQSSQPSSSSQPSPSQSSQPSSSSQPSPSQ

以下是一个仅包含一个可能不匹配的示例：

>>> s = 'SSPQQQQPSSSSQQQSSQPSPSQSSQPSSQPPSSSSQPSPSQSSQPSSSSQPSPSQSSQPSSSSQPSPSQ'
>>> re.findall(r'(?=(SSQP|[A-Z]SQP|S[A-Z]QP|SS[A-Z]P|SSQ[A-Z]))', s)
['SSQQ', 'SSQP', 'SSQP', 'SSQP', 'SSQP', 'SSQP', 'SSQP', 'SSQP', 'SSQP']

显然，在上面的代码中合并两个不匹配的可能性需要对所有可能的组合进行大量的暴力输入。在

如何扩展此代码（或重构此代码）以探索两个不匹配的可能性？在

此外，我想修改我的输出，以便获得返回的数字索引（不是SSQQ或{}），它与子字符串匹配。在

Answer 1

组合爆炸并不意味着4个错误中有2个不匹配。在

首先，请注意，您可以省略SSQP本身，因为它包含了所有更宽泛的情况。在

re.findall(r'(?=([A-Z]SQP|S[A-Z]QP|SS[A-Z]P|SSQ[A-Z]))', s)

所以，案件数量是

^{pr2}$

对于最多两个不匹配，案例数为

               4!
C(4, 2) = ––––––––––––– = 6
          2! * (4 - 2)!

也就是说

re.findall('(?=(SS..|S.Q.|S..P|.SQ.|.S.P|..QP))', s)

（为了简化说明，我冒昧地写了.，而不是{}。）

---

要获取匹配项的位置而不是匹配项的文本：

[match.start(0) for match in re.finditer('(?=(SS..|S.Q.|S..P|.SQ.|.S.P|..QP))', s)]

Answer 2

您不必使用re，这里可以使用^{}模块，节省大量内存。在

您可以先提取长度为4的所有子字符串，然后将它们与您的substring进行比较，只需选择那些与您的substring差别小于2的子字符串：

from itertools import izip,islice,tee

def sub_findre(s,substring,diffnumber):
    sublen=len(substring)
    zip_gen=(izip(substring,islice(s,i,i+sublen)) for i in xrange(len(s)))
    for z in zip_gen:
        l,z=tee(z)
        if sum(1 for i,j in l if i==j)>=sublen-diffnumber:
            new=izip(*z)
            next(new)
            yield ''.join(next(new))

演示：

^{pr2}$

如果要返回索引，则需要将索引放在izip中，可以使用itertools.repeat()重复长度为substring的索引：

from itertools import izip,islice,tee,repeat

def sub_findre(s,substring,diffnumber):
    sublen=len(substring)
    zip_gen=(izip(substring,islice(s,i,i+sublen),repeat(i,sublen)) for i in xrange(len(s)))
    for z in zip_gen:
        l,z=tee(z)
        if sum(1 for i,j,_ in l if i==j)>=sublen-diffnumber:
            new=izip(*z)
            next(new)
            next(new)
            yield next(new)[0]

演示：

print list(sub_findre(s,substring,2))
[0, 1, 4, 8, 9, 10, 11, 15, 20, 23, 27, 28, 32, 33, 34, 39, 42, 46, 47, 48, 53, 56, 60, 61, 62, 67]