Efficient solution for Sublist search in python

Question

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

From the same site: https://www.geeksforgeeks.org/python-check-if-one-list-is-subset-of-other/ — PM 77-1, Jun 20 '20 at 18:53
Does this answer your question? [How can I verify if one list is a subset of another?](https://stackoverflow.com/questions/16579085/how-can-i-verify-if-one-list-is-a-subset-of-another) — PM 77-1, Jun 20 '20 at 18:54

Xinyi Li · Answer 1 · 2022-09-11T10:05:04.630

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.

score 0 · Answer 2 · answered Jun 20 '20 at 18:55

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')

score 0 · Answer 3 · answered Jun 20 '20 at 19:25

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

Efficient solution for Sublist search in python

3 Answers3