在Python中查找列表中的子列表

Question

我有一串数字

l = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 2, 1, 1, 2, 0, 0, 0, 0]
[0, 0, 2, 1, 1, 2, 2, 0, 0, 1]
[0, 0, 1, 2, 2, 0, 1, 0, 0, 2]
[1, 0, 1, 1, 1, 2, 1, 0, 2, 1]]

比如，我需要查找一个模式 '2,1,1,2'，我们可以看到这个模式出现在第6行和第7行。为了找到这个序列，我尝试把每个列表转换成字符串，然后去搜索这个模式，但不知道为什么代码没有成功。

import re
for i in l:
 if re.search('2,1,1,2' , str(i).strip('[').strip(']')): print " pattern found"

我是不是漏掉了什么？

Answer 1

l = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 2, 1, 1, 2, 0, 0, 0, 0],
[0, 0, 2, 1, 1, 2, 2, 0, 0, 1],
[0, 0, 1, 2, 2, 0, 1, 0, 0, 2],
[1, 0, 1, 1, 1, 2, 1, 0, 2, 1]]
import re
for i in l:
    if re.search('2, 1, 1, 2' , str(i).strip('[').strip(']')): 
        print " pattern found"

str(list) 这个命令会把列表里的元素变成一个字符串，并且元素之间会有空格。你应该找的是 '2, 1, 1, 2' 这样的格式，而不是 2,1,1,2 这种没有空格的形式。

Answer 2

我建议你使用 Knuth-Morris-Pratt 算法。我想你可能是默认你的模式在列表中只出现一次，或者你只是想知道它是否存在。

如果你想要找出每个开始这个序列的第一个元素，那么你可以使用 KMP。可以把它想象成是列表的一个类似于字符串查找的功能。

希望这对你有帮助。

Answer 3

把你的列表转换成字符串其实不是个好主意。

那我们可以试试这样的做法：

def getsubidx(x, y):
    l1, l2 = len(x), len(y)
    for i in range(l1):
        if x[i:i+l2] == y:
            return i