如何在Python中合并重叠的字符串？

Question

我有一些绳子，

['SGALWDV', 'GALWDVP', 'ALWDVPS', 'LWDVPSP', 'WDVPSPV']

这些字符串彼此部分重叠。如果您手动重叠它们，您将得到：

SGALWDVPSPV

我想要一种从重叠字符串列表到 python 中的最终压缩字符串的方法。我觉得这一定是一个已经有人解决的问题，并且正在努力避免重新发明轮子。我现在可以想象的方法要么是蛮力，要么是通过使用biopython和序列比对器变得比我想要的更复杂。我有一些简单的短字符串，只想以简单的方式正确合并它们。

有没有人有关于在 python 中执行此操作的好方法的建议？谢谢！

Answer 1

这是一个快速排序的解决方案：

s = ['SGALWDV', 'GALWDVP', 'ALWDVPS', 'LWDVPSP', 'WDVPSPV']
new_s = sorted(s, key=lambda x:s[0].index(x[0]))
a = new_s[0]
b = new_s[-1]
final_s = a[:a.index(b[0])]+b

输出：

'SGALWDVPSPV'

该程序s按每个元素的第一个字符的索引值进行排序，试图找到使第一个元素和所需输出之间的重叠距离最大化的字符串。