Encontrar una inserción en una cadena

Question

¿Cuál es la mejor forma de comprobar si StringA = StringB con otro StringC insertado en algún punto arbitrario?

Por ejemplo, dada abcdef y abcXYZdef, quiero encontrar que abcXYZdef es abcdef con XYZ inserta en la posición 4.

Por otra parte, dado abcdef y abRSTcdXYZef, quiero encontrar que la primera cadena no se puede convertir en el segundo con solo una inserción.

Sé que podría examinar StringA carácter por carácter, desde ambos extremos, y comprobar si cubre la totalidad de StringB, pero sería tedioso escribirlo. También sería bastante lento hacer esto en Python (en el que estoy trabajando) y preferiría no escribir una extensión C especial solo para esto.

¿Hay alguna cosa inteligente que pueda hacer con Regex u otras funciones estándar de manipulación de cadenas que puedan hacer esto por mí?

editar: Para aclarar, StringC es completamente desconocido; Puede que ni siquiera haya un StringC válido, y querré saber si ese es el caso.

Answer 1

Una joya muy poco apreciada en el lib estándar es 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

No lo sé, pero está tratando de encontrar la "distancia de edición". Comprobación de Wikipedia:

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

También puede buscar en el corrector de ortografía de Peter Norvig:

http://norvig.com/spell-correct.html

Creo que se podría adaptar el código del corrector de ortografía para hacer lo que necesita.

Buena suerte.

Answer 3

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

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

Posiblemente? Probando en este momento ...

Answer 4

Esto ... parece kludgy hasta cierto punto, y es probable que solo esté a mitad de camino, pero parece que encontró la subcadena en tu ejemplo y probablemente podría expandirse un poco. Puedo revisar que algunos en un minuto con un poco más de tiempo para probar, pero es un concepto enfoque:

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 

no me gusta el uso de range(len()), pero en este escenario de uso particular, creo que es apropiado. Imprimirá el índice donde tuvo lugar una inserción si una sola inserción convertirá s1 en s2.

Answer 5

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 6

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) 

y ejemplos ...

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