Sublist Search-(Search a linked list in another list)

Sublist search is used to detect a presence of one list in another list. Suppose we have a single-node list (let’s say the first list), and we want to ensure that the list is present in another list (let’s say the second list), then we can perform the sublist search to find it. For instance, the first list contains these elements: 23 -> 30 -> 41, and the second list contains these elements: 10 -> 15 -> 23 -> 30 -> 41 -> 49. At a glance, we see that the first list presents in the second list.

The sublist search algorithm works by comparing the first element of the first list with the first element of the second list. If the two values don’t match, it goes to the next element of the second list. It does this until the two values match, then checks the succeeding elements of the first list with the succeeding elements of the second list. If all elements match, then it returns true, otherwise, it returns false.
Time Complexity: O(m*n) where m is the number of nodes in second list and n in first.

Approach:

1. Take first node of second list.
2. Start matching the first list from this first node.
3. If whole lists match return true.
4. Else break and take first list to the first node again.
5. And take second list to its second node.
6. Repeat these steps until any of linked lists becomes empty.
7. If first list becomes empty then list found else not.

CODE

def is_Sublist(l, s):
	sub_set = False
	if s == []:
		sub_set = True
	elif s == l:
		sub_set = True
	elif len(s) > len(l):
		sub_set = "LIST NOT FOUND"

	else:
		for i in range(len(l)):
			if l[i] == s[0]:
				n = 1
				while (n < len(s)) and (l[i+n] == s[n]):
					n += 1
				
				if n == len(s):
					sub_set = "LIST FOUND"

	return sub_set

a = [2,4,3,5,7]
b = [4,3]
print(is_Sublist(a, b))

Output:                LIST FOUND