Reputation: 169
Hi I'm trying to do a sub-list search algorithm in python that I found here, need some efficient solutions in terms of time complexity. What I tried is:
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
Upvotes: 0
Views: 183
Reputation: 1022
See Knuth–Morris–Pratt algorithm, which has the time complexity of $O(n)$
One possible implementation:
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
can be used as the sub-list to check while text
can be used as the entire list.
Upvotes: 1
Reputation: 27577
Here is what you can do:
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')
Output:
found
Another way:
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')
Output:
found
Upvotes: 0
Reputation: 21
Convert l1
and l2
to strings, and then do the search:
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')
Upvotes: 0