python - 如何在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'}