Python-如何找到两个字符串的所有交集？ [英] Python - how to find all intersections of two strings?

问题描述

如何查找两个字符串的所有交集（也称为最长公共子字符串）及其在两个字符串中的位置？

How to find all intersections (also called the longest common substrings) of two strings and their positions in both strings?

例如，如果 S1 = never 和 S2 = forever ，则所得交集必须为 [ ever] ，其位置为 [（1,3）] 。如果 S1 = address 和 S2 = oddness ，则所得交集为 [ dd， ess] 及其位置为 [（1,1），（4,4）] 。

For example, if S1="never" and S2="forever" then resulted intersection must be ["ever"] and its positions are [(1,3)]. If S1="address" and S2="oddness" then resulted intersections are ["dd","ess"] and their positions are [(1,1),(4,4)].

最优选的解决方案是不包含任何库。但是也欢迎任何正确的解决方案。

Shortest solution without including any library is preferable. But any correct solution is also welcomed.

推荐答案

好，您是说您不能包含任何库。但是，Python的标准 difflib 包含的功能完全符合您的期望。考虑到这是一个Python面试问题，对difflib的熟悉可能是面试官所期望的。

Well, you're saying that you can't include any library. However, Python's standard difflib contains a function which does exactly what you expect. Considering that it is a Python interview question, familiarity with difflib might be what the interviewer expected.

In [31]: import difflib

In [32]: difflib.SequenceMatcher(None, "never", "forever").get_matching_blocks()
Out[32]: [Match(a=1, b=3, size=4), Match(a=5, b=7, size=0)]


In [33]: difflib.SequenceMatcher(None, "address", "oddness").get_matching_blocks()
Out[33]: [Match(a=1, b=1, size=2), Match(a=4, b=4, size=3), Match(a=7, b=7, size=0)]

您总是可以忽略最后一个Match元组，因为（根据文档）是虚拟的。

You can always ignore the last Match tuple, since it's dummy (according to documentation).

这篇关于Python-如何找到两个字符串的所有交集？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！