在python中搜索子列表的有效解决方案

Question

嗨，我正在尝试用 python 做一个我在这里找到的子列表搜索算法，在时间复杂度方面需要一些有效的解决方案。 我尝试的是：

l1 = [1,2,3,4]
l2 = [3,5,6,1,2,3,4,6]
l1_index = 0
l = len(l1)
sublist = []
for i in range(len(l2)):
if l1[l1_index] == l2[i]:
sublist.append(l2[i])
l1_index += 1
print("found")
if len(sublist) == l:
break
continue
else:
print("not found")
l1_index = 0

Answer 1

参见Knuth-Morris-Pratt算法，其时间复杂度为$O(n($

一种可能的实现：

def kmp(pattern, text):
n = len(pattern)
m = len(text)
next_v = [0] * n
for i in range(1, n):
j = next_v[i - 1]
while j > 0 and pattern[i] != pattern[j]:
j = next_v[j - 1]
if pattern[i] == pattern[j]:
j += 1
next_v[i] = j
j = 0
for i in range(m):
while j > 0 and text[i] != pattern[j]:
j = next_v[j - 1]
if text[i] == pattern[j]:
j += 1
if j == n:
return i - n + 1
return -1

pattern可以用作要检查的子列表，而text可以用作整个列表。

Answer 2

将l1和l2转换为字符串，然后执行搜索：

l1 = [1,2,3,4]
l2 = [3,5,6,1,2,3,4,6]
l1 = str(l1)
l2 = str(l2)
# This will return a string of the data only without the '[',']'
l1 = l1.split('[')[1].split(']')[0]
l2 = l2.split('[')[1].split(']')[0]
# Using string find function
if l2.find(l1) > 0 :
print('l1 is a sublist of l2')

Answer 3

以下是您可以执行的操作：

l1 = [1,2,3,4]
l2 = [3,5,6,1,2,3,4,6]
found = False
for i in range(len(l2)-len(l1)+1):
if l2[i:i+len(l1)] == l1:
found = True
if found:
print('found')
else:
print('not found')

输出：

found

---

另一种方式：

l1 = [1,2,3,4]
l2 = [3,5,6,1,2,3,4,6]
if str(l1)[1:-1] in str(l2)[1:-1]:
print('found')
else:
print('not found')

输出：

found