字符串正則表達式兩個不匹配Python

Question

如何擴展下面的代碼以允許我探索所有的情況下，我的子字符串和父字符串之間有2個不匹配或更少？

子串：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或SSQP）。

Answer 1

您不必使用re在這裏你可以使用itertools模塊而是節省大量的內存。

您可以先提取所有子串長度爲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)) 

演示：

s='SSPQQQQPSSSSQQQSSQPSPSQSSQPSSQPPSSSSQPSPSQSSQPSSSSQPSPSQSSQPSSSSQPSPSQ' 

substring='SSQP' 
print list(sub_findre(s,substring,2)) 

['SSPQ', 'SPQQ', 'QQQP', 'SSSS', 'SSSQ', 'SSQQ', 'SQQQ', 'SSQP', 'PSQS', 'SSQP', 'SSQP', 'SQPP', 'SSSS', 'SSSQ', 'SSQP', 'PSQS', 'SSQP', 'SSSS', 'SSSQ', 'SSQP', 'PSQS', 'SSQP', 'SSSS', 'SSSQ', 'SSQP', 'PSQ'] 

如果您想要返回索引，您需要將索引放入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] 

Answer 2

組合爆炸不是對於四個中的兩個不匹配不好。

首先，請注意，您可以省略SSQP本身，因爲它涵蓋了所有較寬鬆的情況。

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

所以，病例數是

   4! 
C(4, 1) = ––––––––––––– = 4 
      1! * (4 - 1)! 

對於最多兩個錯配，病例數是

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

即，

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

（要簡化了插圖，我冒昧了。寫.代替[A-Z]）

---

要獲得比賽的，而不是匹配的文本的位置：

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