在字符串中查找插入点

Question

需要在任意位置插入另一个字符串C时，如何检查StringA和StringB是否相等？例如，给定abcdef和abcXYZdef，我想找到abcXYZdef是在位置4插入XYZ后的abcdef。另一方面，如果给定abcdef和abRSTcdXYZef，我想找到第一个字符串不能仅通过单个插入被转换为第二个字符串。 我知道可以逐个字符地从两端检查StringA，然后检查它是否覆盖整个StringB，但编写这种代码会非常繁琐。使用Python（我的工作语言）做到这一点也会相当慢，并且我不希望为此编写特殊的C扩展程序。有没有一些聪明的方法可以使用正则表达式或其他标准字符串操作函数来完成这项任务？ 编辑：请注意，完全不知道StringC的内容；甚至可能没有有效的StringC，我需要知道这种情况是否存在。

- Li Haoyi

---

如果您把示例字符串缩短并使其更易于理解，那可能会有所帮助。 - Paul Sasik

你真的认为写起来会很繁琐吗？Python有很好的切片功能，可以用于检查子字符串s1[:n]==s2[:n]。当然，它并不是非常高效，但我认为编写它不会花费太长时间。 - phimuemue

我不知道为什么你会毫不考虑地拒绝逐个字符的解决方案。这似乎不会超过几行代码，并且它的速度几乎可以达到纯Python的极限。 - Mark Ransom

@mark：主要是因为我将处理大小可能达到100KB的文本字符串；我希望使用比纯Python更快的东西 =D。 - Li Haoyi

如果你需要更快的速度，使用C/C++实现逐字符比较可能会非常快。但首先，请查看我下面的Python实现，看看它是否足够快。 - Mark Ransom

Answer 1

标准库中一个被低估的宝石是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)]

- pyroscope

---

+1 是因为介绍了 difflib，但解释如何解读结果会更有帮助。 - neurino

@neurino - 每个元组代表一个匹配块；第一个数字是第一个序列中的起始偏移量，第二个数字是第二个序列中的起始偏移量，最后一个数字是匹配块的长度。 - Ben Blank

不错！从来不知道有这个库。 - Li Haoyi

哇... 确实是内置电池！ - steveha

Answer 2

这种方法在某种程度上感觉有些笨拙，而且它只完成了一半，但看起来它找到了你的示例中的子字符串，可能还可以进一步扩展。我可以稍微修改一下，并进行更多测试，但这只是一个概念性的方法：

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，则它将打印插入发生的索引。

- g.d.d.c

---

为什么你不喜欢使用 range(len())？ - krs1

@krs1 - 这通常不符合“pythonic”的风格...通常，您直接迭代一个可迭代对象，或者如果必须使用索引值，则使用enumerate(iterable)使其可用。尽管如此，在这种情况下，这样做可能是适当的。 - g.d.d.c

Answer 3

我不知道，但你正在尝试寻找“编辑距离”。查看维基百科：

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

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

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

我认为你可以从拼写纠正器中调整代码以满足你的需求。

祝好运。

- steveha

---

最长公共子串 - Randy

Answer 4

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)

- Mark Ransom

Answer 5

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)

- Andrew Clark

Answer 6

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

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

可能吗？正在进行测试...

- krs1

---

我认为strC不是一个已知的值 - 这就是他试图确定的内容。如果它是已知的，那么就没有提出这个问题的理由。 - g.d.d.c