CODEWITHSUNDEEP
python
vineet singh
vineet singh

Reputation: 169

Efficient solution for Sublist search in python

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

Answers (3)

Xinyi Li
Xinyi Li

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

Red
Red

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

AKHILESH A S
AKHILESH A S

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

Related Questions