文字列への挿入の検索

Question

StringA = StringBと任意のポイントに挿入された別のStringCをチェックする最良の方法は何ですか？例えば

は、abcdefとabcXYZdefを与え、私はabcXYZdefが一方の位置4.

に挿入XYZとabcdefであることを見つけたい、abcdefとabRSTcdXYZefを与え、私は最初の文字列を検索するを1回の挿入で2番目にすることはできません。

私はStringAの文字を両端から渡して、StringB全体をカバーしているかどうかを確認できますが、それは書くのが面倒です。 Python（これは私が取り組んでいる）でこれをやるのがやや遅く、ちょうどこれのために特別なC拡張を書くのではないでしょう。

Regexや他の標準の文字列操作関数を使って私にできることはありますか？

編集：明確にするために、StringCは完全に不明です。有効なStringCもないかもしれませんが、そうであるかどうかを知りたいです。

Answer 1

標準libに非常に過小評価宝石が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

私は分かりませんが、あなたは "編集距離"を見つけようとしています。ウィキペディアの確認：あなたはまた、ピーター・ノーヴィグのスペル訂正で見えるかもしれません

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

これは...ある程度のクルージングを感じていますが、それはおそらく半分しかありませんが、あなたの例の部分文字列が見つかったようです。私がテストするために、いくつかのより多くの時間と分でいくつかを修正することができますが、それはアプローチのコンセプトです：

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())の使用を好きではないが、この特定の使用シナリオでは、私はそれが適切だと思います。 1回の挿入でs1が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) 

と例...

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