如何在其他python 3中找到与最后n个字符串匹配的第一个n个字符串之间的重叠？

Question

假设我有两个字符串：

a = 'stackoverflow'
b =  'mathisgoodstackover'

我试图从a的开头找到与b结尾相匹配的最大重叠部分。

c= 'stackover'
d = 'stackoverf'

c是最优解。d不是，因为b没有以stackoverf结尾。

我试着用蛮力，但不知道怎么写循环。有有效的算法吗？

谢谢,

Answer 1

您可以使用内置函数max和列表理解：

max([a[:i] for i in range(1,len(a) + 1) if b.endswith(a[:i])], key=len)

产出：

'stackover'

也适用于特殊情况：

a = 'ssss'
b =  'mathisgoodssssss'
max([a[:i] for i in range(1,len(a) + 1) if a[:i] == b[-i:]], key=len)

外：

'ssss'

或者按照@ShadowRanger的建议，您可以从尽可能大的i开始，然后使用带有生成器表达式的下一首内置函数进行收缩。

next((a[:i] for i in range(len(a), 0,-1) if b.endswith(a[:i])), '')