提问人：HTF-struggle 提问时间：10/27/2023 最后编辑：Marco BonelliHTF-struggle 更新时间：10/27/2023 访问量：42
查找 python 列表/numpy 数组之间的最长重叠（非交集）
Find longest overlap between python lists / numpy arrays (not intersection)
问：
我想知道是否有一种有效的方法来找到列表或 numpy 数组（内置函数、列表推导或其他简短方法）之间的最长（或任何/每个）重叠。我已经读过关于使用集合来查找列表/数组的交集（出现在两者中的元素），但我需要找到出现在两者中的（最长/所有）公共序列（子列表/数组）。转向其他数据类型以帮助实现这一点是一种选择。
例：
list1 = [1,2,3,5,4,6,9,8]
list2 = [3,8,2,3,5,4,1,2]
overlap = find_overlap(list1,list2) # function find_overlap TBD
# overlap == [2,3,5,4]
示例中两个列表的交集将返回 [1,2,3,4,5,8]。但是，这返回了所有公共元素，而不是我需要的公共序列。
我试图找到内置函数，但没有成功。我也没有发现这里有人提出类似的问题。我可以编写一个迭代或递归函数来尝试实现这一点，但我担心遇到大型（>100.000 个项目）大小列表/数组的爆炸性计算时间。
答：
0赞
blhsing
10/27/2023
#1
您可以使用 difflib。SequenceMatcher.find_longest_match：
from difflib import SequenceMatcher
list1 = [1,2,3,5,4,6,9,8]
list2 = [3,8,2,3,5,4,1,2]
match = SequenceMatcher(None, list1, list2).find_longest_match()
print(list1[match.a: match.a + match.size])
这将输出：
[2, 3, 5, 4]
评论