用python中的公共子字符串连接字符串？

Question

输入

ONESTRING
STRINGTHREE
THREEFOUR 
FOURFIVE

输出

ONESTRINGTHREEFOURFIVE

在python中

我认为首先我用2个字符串连接，然后运行一个循环，但这会产生一个错误，我不知道为什么有人能在python中提供帮助

Answer 1

下面是根据您提供的示例的通用解决方案。必须对顺序进行排序，否则它将不起作用

from functools import reduce

s = [
    "ONESTRING",
    "STRINGTHREE",
    "THREEFOUR",
    "FOURFIVE",
]

def join_f(first, add):
    i = 1
    while add[:i] in first:
        i += 1
    return first + add[i-1:]

print(reduce(join_f, s))

Answer 2

可以使用difflib库，示例代码供您参考

from difflib import SequenceMatcher

str1 = "ONESTRING"
str2 = "STRINGTHREE"

match = SequenceMatcher(None, str1, str2).find_longest_match(0, len(str1), 0, len(str2))
#match[a]=3, match[b]=0, match[size]=6

Answer 3

警告

此解决方案适用于按任意顺序排列的字符串列表。这意味着必须检查每对可能的单词是否有公共子字符串，如果字符串列表较大，则可能需要大量内存

解决方案1允许在需要时连接没有公共子字符串的字

import itertools
from typing import Set, Tuple, Dict, List


def get_match(pair: Tuple[str, str], min_overlap: int = 3) -> str:
    a, b = pair
    for i in range(min_overlap, min(map(len, pair)) + 1):
        if a[-i:] == b[:i]:
            return b[:i]
    return ""


def links_joiners(strings: List[str]) -> Tuple[Dict[str, str], Set[str]]:
    links, joiners = dict(), set()
    for pair in itertools.permutations(strings, 2):
        if (match := get_match(pair)):
            joiners.add(match)
            links.update((pair,))
    return links, joiners


def get_ordered_strings(strings: List[str], links: Dict[str, str]) -> List[str]:
    def find_order(node: str) -> int:
        return 0 if node not in links else 1 + find_order(links[node])
    return sorted(strings, key=find_order, reverse=True)


def join_strings(strings: List[str], joiners: Set[str]) -> str:
    s = "".join(strings)
    for j in joiners:
        s = s.replace(j, "", 1)
    return s

用法：

strings = ["THREEFOUR",
           "ONESTRING",
           "STRINGTHREE",
           "FOURFIVE"]

links, joiners = get_links_and_joiners(strings)
ordered_strings = get_ordered_strings(strings, links)
join_strings(ordered_strings, joiners)

输出：

'ONESTRINGTHREEFOURFIVE'

解释

首先，itertools是标准库的一部分；无需为此解决方案安装任何第三方软件包

现在，links_joiners()函数将获取字符串列表，并查找具有匹配后缀前缀对的所有字符串对，将这些字符串对放入links字典，如下所示：

{'ONESTRING': 'STRINGTHREE',
 'THREEFOUR': 'FOURFIVE',
 'STRINGTHREE': 'THREEFOUR'}

请注意，这些都不符合顺序。这是因为对于任意的字符串列表，我们首先不能确定字符串是否有序，因此我们必须彻底地迭代strings的每个排列，以确保覆盖了所有对

现在，注意还有一个名为get_ordered_strings()的函数，其中包含一个内部函数find_order()。函数get_ordered_strings()形成了所谓的闭包，但现在理解它并不特别重要。find_order()函数是递归函数，其工作原理如下：

1. 给定一个node，如果node不是links字典中的一个键，我们已经到达了基本大小写并返回零。否则，请转至步骤2

2. 如果node存在，则向该新节点上对find_order的递归调用添加一个

因此，给定一个键，比如"ONESTRING"，find_order()函数将查看与该键关联的值，如果该值也是字典中的键，则查看它的值，依此类推，直到它达到一个不是字典中键的值

下面是find_order()的代码：

def find_order(node: str) -> int:
    if node not in links:
        return 0
    return 1 + find_order(links[node])

下面是调用links_joiners()后links的样子：

{'ONESTRING': 'STRINGTHREE',
 'THREEFOUR': 'FOURFIVE',
 'STRINGTHREE': 'THREEFOUR'}

现在跟踪对find_order("ONESTRING")的示例调用：

find_order("ONESTRING") = 1 + find_order("STRINGTHREE")
                        = 1 + (1 + find_order("THREEFOUR"))
                        = 1 + (1 + (1 + find_order("FOURFIVE")))  # Base case
                        = 1 + (1 + (1 + 0))
                        = 3

此函数所做的是查找给定起始字符串可以进行多少成对连接。另一种思考方式是links实际上表示a DAG中的邻接

基本上，我们要做的是获取节点THREEFOUR、ONESTRING、STRINGTHREE、FOURFIVE，并从它们中构造尽可能长的单链表（一种DAG）：

ONESTRING -> STRINGTHREE -> THREEFOUR -> FOURFIVE

通过将该图的给定“节点”传递给find_order()，它将一直跟随该图直到结束。所以ONESTRING要走3的距离才能到达终点，而THREEFOUR只走1的距离

Node:   ONESTRING -> STRINGTHREE -> THREEFOUR -> FOURFIVE
Dist:       3             2             1            0

现在，通过将find_order传递给内置的sorted()函数，我们可以告诉Python我们希望如何对strings进行排序，在本例中，排序顺序与距离相反。结果是：

>>> strings = ['THREEFOUR', 'ONESTRING', 'STRINGTHREE', 'FOURFIVE']
>>> ordered_strings = get_ordered_strings(strings, links)
>>> ordered_strings
['ONESTRING', 'STRINGTHREE', 'THREEFOUR', 'FOURFIVE']

现在，通过使用公共子字符串连接每个字符串，我们正在构造可能最长的字符串，其中约束条件是每对字符串必须在正确的位置有一个公共子字符串。换句话说，ordered_strings表示DAG中的最长路径。或者更准确地说，我们已经设计了一个具有最长路径的DAG，方法是使用所有提供的节点，并将它们按正确的顺序排列

从这里，我们连接每个字符串：

>>> s = "".join(ordered_strings)
>>> s
'ONESTRINGSTRINGTHREETHREEFOURFOURFIVE'

然后，我们删除每个Joiner的一个实例：

for j in joiners:
    s = s.replace(j, "", 1)

解决方案2，仅连接重叠字符串

此解决方案重用上面的join_strings()和get_match()。它还使用了walrus操作符:=（python3.8+），但是不用它就可以很容易地编写

def join_overlapping_pairs(strings: List[str]) -> str:
    if len(strings) == 1:
        return strings.pop()
    matches = set()
    for pair in itertools.permutations(strings, 2):
        if (match := get_match(pair)):
            matches.add(join_strings(pair, (match,)))
    return join_overlapping_pairs(matches)