문자열에서 삽입 찾기

Question

임의의 지점에 다른 StringC가 삽입 된 상태에서 StringA = StringB인지 확인하는 가장 좋은 방법은 무엇입니까? abcdef 및 abcXYZdef 주어진 예를 들어

가, 내가 abcXYZdef이 XYZ와 abcdef이, 다른 한편으로 위치 4.

에 삽입 abcdef 및 abRSTcdXYZef 주어진 것을 알게 싶어, 내가 찾으려는 그 첫 번째 문자열 을 한 번만 삽입하면 두 번째로 바뀔 수 없습니다.

나는 StringA 문자를 양쪽 끝에서 문자로 갈 수 있고 StringB 전체를 덮고 있는지 확인할 수 있지만 쓸데는 지루할 것이다. 파이썬에서이 작업을 수행하는 것이 다소 느리고 (필자가 작업하고있는) 파이썬에서는 특별한 C- 확장을 작성하지 않을 것입니다.

나를 위해이 작업을 수행 할 수있는 Regex 또는 다른 표준 문자열 조작 기능으로 수행 할 수있는 똑똑한 작업이 있습니까?

편집 : 명확히하기 위해 StringC는 완전히 알려져 있지 않습니다. 유효한 StringC조차 없을 수도 있습니다. 그렇다면 그 사실을 알고 싶을 것입니다.

Answer 1

매우 과소 보석은 ...

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

잘 모르겠지만 "거리 편집"을 찾으려고합니다. 위키 백과 확인 : 또한 피터 노르 빅의 맞춤법 교정기 볼 수

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

:

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

난 당신이 당신이 필요로 할 맞춤법 교정기의 코드를 적응할 수 있다고 생각.

행운을 빈다.

Answer 3

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

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

아마도? 지금 테스트 중입니다 ...

Answer 4

...이 정도면 ... kludgy도 느껴질 것입니다. 아마도 절반 정도 밖에 안되지만, 예제의 하위 문자열을 발견하고 조금 확장 할 수있는 것처럼 보입니다. 나는 테스트하기 위해 좀 더 시간 분에 일부를 수정할 수 있지만, 접근 개념이다 :

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로 바뀌면 삽입이 발생한 위치의 색인이 인쇄됩니다. 표준 lib 디렉토리에

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) 

그리고 예 ... 당신이 당신의 샘플을 만든 경우

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