python - 2 つの Python リストで共通のスライスを見つける

Question

2 つの Python リストで共通のスライスを見つけたいと思います。

例えば：

list1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

list2 = [0, 0, 3, 4, 5, 0, 0, 8, 9, 0]

[3, 4, 5] と [8,9] の 2 つのリストを返す必要があります。

0 の代わりに任意の数字または文字を使用できます。

Answer 1

使用difflib.SequenceMatcher:

>>> import difflib
>>> list1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> list2 = [0, 0, 3, 4, 5, 0, 0, 8, 9, 0]
>>> matcher = difflib.SequenceMatcher(a=list1, b=list2)
>>> match = matcher.find_longest_match(0, len(list1), 0, len(list2))
>>> match
Match(a=2, b=2, size=3)
>>> print list1[match.a:match.a+match.size]
[3, 4, 5]

SequenceMatcher.find_longest_match() は、そのシーケンス (alo、ahi、blo、bhi) ごとに開始インデックスと終了インデックスを取得するため、一致を見つけた後find_longest_match()、同じmatcherオブジェクトを呼び出すことができますが、パラメーターを微調整して、前の一致を調べ始めることができます。

これをループで行うことができます。これを行う関数を次のように記述します。

import difflib
def common_slices(a, b):
    matcher = difflib.SequenceMatcher(a=a, b=b)
    sa, sb, size = matcher.find_longest_match(0, len(a), 0, len(b))
    while size != 0:
        if size > 1:
            yield a[sa:sa+size]
        sa, sb, size = matcher.find_longest_match(sa+size, len(a), sb+size, len(b))

>>> list(common_slices(list1, list2))
[[3, 4, 5], [8, 9]]

Answer 2

>>> from itertools import groupby
>>> from operator import itemgetter
>>> list1
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> list2
[0, 0, 3, 4, 5, 0, 0, 8, 9, 0]
>>> [[e[0] for e in v]
     for k,v in groupby(((a ,b, a==b)
             for a,b in zip(list1, list2)), itemgetter(2))
      if k]
[[3, 4, 5], [8, 9]]

@FJが提案するようにdifflibを使用したくない場合は、この方法で使用する必要があります

>>> [list1[match.a: match.a + match.size]
     for match in SequenceMatcher(None,list1,list2).get_matching_blocks()[:-1]]

ただし、これは以前の線形ソリューションよりもはるかに非効率的であることを覚えておいてください