在字符串中查找插入

Question

检查StringA=StringB是否在任意点插入另一个StringC的最佳方法是什么？在

例如，给定abcdef和abcXYZdef，我想发现abcXYZdef是abcdef，在位置4插入了XYZ。在

另一方面，给定abcdef和abRSTcdXYZef，我想发现第一个字符串不能通过一次插入就变成第二个字符串。在

我知道我可以逐字逐句地从两端检查StringA，看看它是否涵盖了StringB的全部内容，但这样写起来会很乏味。用Python（我正在使用Python）做这件事也会很慢，我不想为此编写一个特殊的C扩展。在

对于Regex或其他标准的字符串操作函数，我能做些什么吗？在

编辑：澄清一下，StringC是完全未知的；甚至可能没有一个有效的StringC，我想知道是不是这样。在

Answer 1

这个。。。在某种程度上感觉很模糊，而且它可能还只是一半，但是它似乎在您的示例中找到了子字符串，并且可能会扩展一点。我可以在一分钟内修改它，但它是一个方法概念：

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 2

标准库中一个非常不受重视的gem是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 3

我不知道，但你想找出“编辑距离”。查看维基百科：

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

你也可以看看彼得·诺维格的拼写更正器：

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

我想你可以根据你的需要修改拼写更正器的代码。在

祝你好运。在