Trovare un inserimento in una stringa

Question

Qual è il modo migliore per verificare se StringA = StringB con un altro StringC inserito in un punto arbitrario?

Ad esempio, dato abcdef e abcXYZdef, voglio scoprire che abcXYZdef è abcdef con XYZ inserito alla posizione 4.

D'altra parte, dato abcdef e abRSTcdXYZef, voglio scoprire che la prima stringa impossibile essere trasformato nel secondo con un solo inserimento.

So che potrei andare su StringA carattere per carattere, da entrambe le estremità, e controllare se copre l'intero StringB, ma sarebbe piuttosto noioso scrivere. Sarebbe anche piuttosto lento farlo in Python (sul quale sto lavorando) e preferirei non scrivere una speciale estensione C solo per questo.

Ci sono delle cose intelligenti che posso fare con Regex o altre funzioni di manipolazione delle stringhe standard che possono farlo per me?

modifica: per chiarire, StringC è completamente sconosciuto; Potrebbe non esserci nemmeno un StringC valido e vorrò sapere se questo è il caso.

Answer 1

Un gioiello molto sottovalutato nel lib standard è 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

Non so, ma stai cercando di trovare "modifica distanza". Controllo Wikipedia:

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

Si potrebbe anche guardare il correttore ortografico di Peter Norvig:

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

Penso che si potrebbe adattare il codice dal correttore ortografico per fare quello che ti serve.

Buona fortuna.

Answer 3

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

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

Possibilmente? Prova subito ...

Answer 4

Questo ... sembra un po 'caotico, ed è probabilmente solo a metà strada, ma sembra che abbia trovato la sottostringa nel tuo esempio e potrebbe probabilmente essere espanso un po'. Posso rivedere ancora un po in un minuto con un po 'più di tempo per testare, ma è un concetto di approccio:

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 

Non mi piace l'uso di range(len()), ma in questo scenario particolare l'uso penso che sia appropriata. Stamperà l'indice in cui è stato effettuato un inserimento se un singolo inserimento trasformerà s1 in 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) 

E esempi ...

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