String regex two mismatches Python

Question

Как я могу расширить код ниже, чтобы позволить мне исследовать все экземпляры, где у меня есть 2 несоответствия или меньше между моей подстрокой и родительской строкой?

Substring: 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 и просто выбрать те, которые имеют менее 2 разница с вашим substring:

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)]