从Python中的两个方向上的两个单词计算单词重叠
问题描述：
所以我有两个单词。我想写一个函数来查找从每个单词到另一个单词的最大重叠。例如：从Python中的两个方向上的两个单词计算单词重叠
words = ['AAB', 'BAA']
find_overlap('AAB', 'BAA')
应该输出B和大小1，并且：
find_overlap('BAA', 'AAB')
应该输出AA和大小2.如何做到这一点有什么建议？
编辑：所以我试着从python difflib.SequenceMatcher，但我不明白输出。
s1 = "AAB"
s2 = "BAA"
s = difflib.SequenceMatcher(None, s1, s2)
pos_a, pos_b, size = s.find_longest_match(0, len(s1), 0, len(s2))
print(pos_a, pos_b, size)
答
对于较短的字符串，一个天真的方法可能就足够了。例如，@Moberg的想法可以实现这样
def largest_overlap(s1,s2):
n = min(len(s1),len(s2))
for i in range(n,0,-1):
if s2.startswith(s1[-i:]):
return s1[-i:]
return ''
一些测试用例：
print("BAA, AAB =>", largest_overlap("BAA", "AAB"))
print("AAB, BAA =>", largest_overlap("AAB", "BAA"))
print("AAA, BB =>", largest_overlap("AAA", "BB"))
print("AA, AABB =>", largest_overlap("AA", "AABB"))
print("hello world, world peace =>", largest_overlap("hello world", "world peace"))
输出：
BAA, AAB => AA
AAB, BAA => B
AAA, BB =>
AA, AABB => AA
hello world, world peace => world
对于更长的字符串，你可能需要一个更复杂的算法，类似于this。
+0
谢谢。我怎样才能修改它输出整个单词没有重叠，例如与BAA，AAB => AA，我也想BAAB。 –
+0
@LoraSinha如果's'是返回的重叠，那么's1 + s2 [len（s）：]'是两个单词连接在一起出现的重叠。 –
首先检查最大可能的重叠，然后重复越来越小的重叠。 – Moberg
@Moberg这表明要检查*战争与和平*和*犯罪与惩罚*完整文本的最大重叠，我们将开始检查数十万个字符的重叠，然后下降。听起来不太有效。重叠可能是长度为0. –
@JohnColeman不，效率不高。尽管这意味着要找到WaP中CaP的第一个字母的第一个出现，并努力向下。一旦它们不匹配，跳到下一次发生的源头。还有什么其他的方式？ :) – Moberg