在Python中找到兩個列表的所有常見序列

Question

我想找到兩個列表中的所有常見序列。 例如：

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

我想輸出：

matched_list = [[1,2],[7,8,9],[5,6]] 

我的代碼如下：

import difflib 
def matches(first_string,second_string): 
    s = difflib.SequenceMatcher(None, first_string,second_string) 
    match = [first_string[i:i+n] for i, j, n in s.get_matching_blocks() if n > 0] 
    return match 

但我得到的輸出：

match = [[1,2] ,[7,8,9]] 

Answer 1

如果輸出訂單不是導入螞蟻，多通解決方案可以做到這一點。每次找到匹配項時，從列表/字符串中刪除子字符串/子列表。

實施

def matches(first_string,second_string): 
    while True: 
     mbs = difflib.SequenceMatcher(None, list1, list2).get_matching_blocks() 
     if len(mbs) == 1: break 
     for i, j, n in mbs[::-1]: 
      if n > 0: yield first_string[i: i + n] 
      del first_string[i: i + n] 
      del second_string[j: j + n] 

樣本輸出

>>> list(matches(list1, list2)) 
[[7, 8, 9], [1, 2], [5, 6]]