Как найти подстроку, если подстрока заменена случайными символами?

Question

Допустим, у нас есть строка в Python:

original_string = "TwasTheNightBeforeChristmasWhenAllThroughTheHouse"

И мы заинтересованы в поиске начальных координат подстроки substring ="ChristmasWhen". Это очень просто в Python, то есть

>>> substring ="ChristmasWhen"
>>> original_string.find(substring)
18

, и это проверяет

>>> "TwasTheNightBeforeChristmasWhenAllThroughTheHouse"[18]
'C'

Если мы попытаемся найти строку, которой не существует, find() будет вернуть -1.

Вот моя проблема:

У меня есть подстрока, которая гарантированно должна быть из исходной строки. Однако символы в этой подстроке были случайно заменены другим символом.

Как можно алгоритмически найти начальную координату подстроки (или, по крайней мере, проверить, если это возможно), если подстрока имеет случайные символы '-', заменяющие определенные буквы?

Вот конкретный пример:

original_string = "TwasTheNightBeforeChristmasWhenAllThroughTheHouse"
substring = '-hri-t-asW-en'

Естественно, если я попытаюсь original_string.find('-hri-t-asW-en'), но было бы возможно найти, что hri начинается в 19, и, следовательно, с префиксом - подстрока original_string.find('-hri-t-asW-en') должна быть 18.

Answer 1

Обычно для этого используются регулярные выражения: найдите шаблоны. Затем вы можете попробовать:

import re                       # use regexp
original_string = "TwasTheNightBeforeChristmasWhenAllThroughTheHouse"
r = re.compile(".hri.t.asW.en") # constructs the search machinery
res = r.search(original_string) # search
print (res.group(0))            # get results

результат будет:

ChristmasWhen

Теперь, если ваш ввод (строка поиска) должен использовать '-' в качестве подстановочного знака, вы можете затем перевести его на получить правильное регулярное выражение:

import re 
original_string = "TwasTheNightBeforeChristmasWhenAllThroughTheHouse"
s = ".hri.t.asW.en"              # supposedly inputed by user
s = s.replace('-','.')           # translate to regexp syntax
r = re.compile(s)
res = r.search(original_string)
print (res.group(0))

Answer 2

Вы можете использовать регулярные выражения, чтобы найти совпадение и возможность

import re
p = re.compile(".hri.t.asW.en")
for m in p.finditer('TwasTheNightBeforeChristmasWhenAllThroughTheHouse'):
    print(m.start(), m.group())

out: (18 ChristmasWhen)

Answer 3

возможно использовать регулярное выражение? Например, вы можете использовать . (точечный символ), чтобы соответствовать любому символу (кроме символа новой строки по умолчанию). Поэтому, если вы измените свою подстроку, чтобы использовать точки вместо штрихов для стертых букв в строке, вы можете использовать re.search, чтобы найти эти шаблоны:

text = 'TwasTheNightBeforeChristmasWhenAllThroughTheHouse';
re.search('.hri.t.asW.en', text)

Answer 4

Подход без регулярных выражений, менее эффективный, чем последний, но все же возможный:

o = "TwasTheNightBeforeChristmasWhenAllThroughTheHouse"
s = '-hri-t-asW-en'
r = next(i for i in range(len(o)-len(s)) if all(a == b or b == '-' for a, b in zip(o[i:i+len(s)], s)))

Выход

18