Поиск вставки в строку

Question

Каков наилучший способ проверки, если StringA = StringB с другим StringC, вставленным в произвольную точку?

Например, учитывая abcdef и abcXYZdef, я хочу найти, что abcXYZdef - это abcdef с XYZ, вставленным в положение 4.

С другой стороны, учитывая abcdef и abRSTcdXYZef, я хочу найти, что первая строка не может быть превращена во вторую только с одной вставкой.

Я знаю, что могу пройтись по символам StringA с обоих концов и проверить, охватывает ли он весь StringB, но написать это было бы довольно утомительно. Также было бы довольно медленно делать это в Python (в котором я работаю), и я бы не стал писать специальное C-расширение только для этого.

Есть ли какие-нибудь умные вещи, которые я могу сделать с помощью Regex или других стандартных функций манипуляции со строками, которые могут сделать это для меня?

edit: чтобы уточнить, StringC полностью неизвестен; Может даже не быть действительного StringC, и я хочу знать, так ли это.

Answer 1

Драгоценный камень в стандартной библиотеке очень недооценен: difflib ...

>>> import difflib
>>> s = difflib.SequenceMatcher(None, "GHSKWITNIFSI", "GHSKWAGDITNIFSI")
>>> s.get_matching_blocks()[:-1]
[(0, 0, 5), (5, 8, 7)]
>>> s = difflib.SequenceMatcher(None, "GHSKWITNIFSI", "GHSKWITNIFSI")
>>> s.get_matching_blocks()[:-1]
[(0, 0, 12)]

Answer 2

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

s1 = 'GHSKWITNIFSI'
s2 = 'GHSKWAGDITNIFSI'

l = len(s2) - len(s1)

for i in range(len(s1)):
 if s2[0:i] + s2[i + l:] == s1:
  print i
  break

Мне не нравится использование range(len()), но в этом конкретном сценарии использования, я думаю,это уместноОн напечатает индекс, в котором произошла вставка, если одна вставка превратит s1 в s2.

Answer 3

from itertools import dropwhile

def get_inserted_substring(s1, s2):
    try:
        # diff is the first index at which the strings differ
        diff = dropwhile(lambda i: s1[i] == s2[i], xrange(len(s2))).next()
        if s2[diff:].endswith(s1[diff:]):
            return (diff, s2[diff:diff-len(s1)])
    except (StopIteration, IndexError):
        # the strings are the same or only differ at the end
        if len(s1) <= len(s2):
            return (len(s1), s2[len(s1):])
    return (None, None)

И примеры ...

>>> get_inserted_substring('abcdef', 'abcXYZdef')
(3, 'XYZ')
>>> get_inserted_substring('abcdef', 'abRSTcdXYZef')
(None, None)
>>> get_inserted_substring('abcdef', 'abcdefXYZ')
(6, 'XYZ')
>>> get_inserted_substring('abcdef', 'XYZabcdef')
(0, 'XYZ')
>>> get_inserted_substring('abcdefXYZ', 'abcdef')
(None, None)

Answer 4

def GetInsertedString(StringA, StringB):
    lenA = len(StringA)
    lenB = len(StringB)
    if lenA > lenB:
        return None, None
    begincount = 0
    while begincount < lenA and StringA[begincount] == StringB[begincount]:
        begincount += 1
    endcount = 0
    while endcount < (lenA - begincount) and StringA[lenA-endcount-1] == StringB[lenB-endcount-1]:
        endcount += 1
    if begincount + endcount != lenA:
        return None, None
    return begincount, StringB[begincount:begincount+lenB-lenA]

>>> GetInsertedString('GHSKWITNIFSI', 'GHSKWAGDITNIFSI')
(5, 'AGD')
>>> GetInsertedString('GHSKWITNIFSI', 'GHSKWAGDTNIFSI')
(None, None)

Answer 5

strA='foor'
strB='foobar'
strC='ba'

if strB.replace(strC,'') == strA:
    print strC,' at index ',len(strB.split(strC)[0])

Возможно?Тестируем прямо сейчас ...

Answer 6

Не знаю, но вы пытаетесь найти «расстояние редактирования».Проверка Википедии:

http://en.wikipedia.org/wiki/Edit_distance

Вы также можете взглянуть на корректор орфографии Питера Норвиг:корректор орфографии, чтобы сделать то, что вам нужно.

Удачи.