如何在python中合并具有重叠字符的字符串？

Question

我正在开发一个python项目,它读取一个URL编码的重叠字符串列表.每个字符串长度为15个字符,并且与其顺序字符串重叠至少3个字符,最多15个字符(相同).

该程序的目标是从重叠字符串列表(有序或无序)到压缩的URL编码字符串.

我当前的方法在重叠字符串中的重复段处失败.例如,我的程序错误地组合:

StrList1 = [ 'd+%7B%0A++++public+', 'public+static+v','program%0Apublic+', 'ublic+class+Hel', 'lass+HelloWorld', 'elloWorld+%7B%0A+++', '%2F%2F+Sample+progr', 'program%0Apublic+']

输出:

output = ['ublic+class+HelloWorld+%7B%0A++++public+', '%2F%2F+Sample+program%0Apublic+static+v`]

当正确的输出是:

output = ['%2F%2F+Sample+program%0Apublic+class+HelloWorld+%7B%0A++++public+static+v']

我使用简单的python,而不是biopython或序列对齐器,虽然也许我应该？

非常感谢有关此事的任何建议或在python中做到这一点的好方法的建议!

谢谢!

Answer 1

您可以从列表中的字符串之一（存储为string）开始，然后对于列表中的每个剩余字符串（存储为candidate），其中：

• candidate是其一部分string，
• candidate包含string,
• candidate的尾巴与头相匹配string，
• 或者，candidate的头部与 的尾部匹配string，

根据两个字符串的重叠方式组装它们，然后递归地重复该过程，从剩余字符串中删除重叠的字符串，并附加组装后的字符串，直到列表中只剩下一个字符串，此时它是一个完全有效的字符串可以添加到最终输出的组装字符串。

由于多个字符串可能有多种方式相互重叠，其中一些可能会产生相同的组装字符串，因此您应该改为输出一组字符串：

def assemble(str_list, min=3, max=15):
    if len(str_list) < 2:
        return set(str_list)
    output = set()
    string = str_list.pop()
    for i, candidate in enumerate(str_list):
        matches = set()
        if candidate in string:
            matches.add(string)
        elif string in candidate:
            matches.add(candidate)
        for n in range(min, max + 1):
            if candidate[:n] == string[-n:]:
                matches.add(string + candidate[n:])
            if candidate[-n:] == string[:n]:
                matches.add(candidate[:-n] + string)
        for match in matches:
            output.update(assemble(str_list[:i] + str_list[i + 1:] + [match]))
    return output

这样就可以使用您的示例输入：

StrList1 = ['d+%7B%0A++++public+', 'public+static+v','program%0Apublic+', 'ublic+class+Hel', 'lass+HelloWorld', 'elloWorld+%7B%0A+++', '%2F%2F+Sample+progr', 'program%0Apublic+']

assemble(StrList1)会返回：

{'%2F%2F+Sample+program%0Apublic+class+HelloWorld+%7B%0A++++public+static+v'}

或者作为具有各种重叠可能性的输入的示例（第二个字符串可以通过位于内部、尾部与头部匹配以及头部与尾部匹配来匹配第一个字符串）：

assemble(['abcggggabcgggg', 'ggggabc'])

会返回：

{'abcggggabcgggg', 'abcggggabcggggabc', 'abcggggabcgggggabc', 'ggggabcggggabcgggg'}