I am quite new and I hope it's not too obvious, but I just can't seem to find a short and precise answer to the following problem.
I have two lists:
a = [2,3,5,2,5,6,7,2]
b = [2,5,6]
I would like to find when all the indexes of the second list (b) are in the first list (a), so that I get something like this:
indexes of b in a: 3, 4, 5 or b = a[3:6]
With a list comprehension:
>>> [(i, i+len(b)) for i in range(len(a)) if a[i:i+len(b)] == b]
[(3, 6)]
Or with a for-loop:
>>> indexes = []
>>> for i in range(len(a)):
... if a[i:i+len(b)] == b:
... indexes.append((i, i+len(b)))
...
>>> indexes
[(3, 6)]
xrange(len(a)), otherwise it won't match the seq if its at the end.
[(i, i+len(b)) for i in range(len(a)-len(b)+1) if a[i:i+len(b)] == b]Also, for efficiency, you can use KMP algorithm that is used in string matching (from here):
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
# create lps[] that will hold the longest prefix suffix
# values for pattern
lps = [0]*M
j = 0 # index for pat[]
# Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps)
i = 0 # index for txt[]
while i < N:
if pat[j] == txt[i]:
i += 1
j += 1
if j == M:
print("Found pattern at index " + str(i-j))
j = lps[j-1]
# mismatch after j matches
elif i < N and pat[j] != txt[i]:
# Do not match lps[0..lps[j-1]] characters,
# they will match anyway
if j != 0:
j = lps[j-1]
else:
i += 1
def computeLPSArray(pat, M, lps):
len = 0 # length of the previous longest prefix suffix
lps[0] # lps[0] is always 0
i = 1
# the loop calculates lps[i] for i = 1 to M-1
while i < M:
if pat[i]== pat[len]:
len += 1
lps[i] = len
i += 1
else:
# This is tricky. Consider the example.
# AAACAAAA and i = 7. The idea is similar
# to search step.
if len != 0:
len = lps[len-1]
# Also, note that we do not increment i here
else:
lps[i] = 0
i += 1
a = [2,3,5,2,5,6,7,2]
b = [2,5,6]
KMPSearch(b, a)
This find the first index of the b in a. Hence, the range is the result of the search and its plus to the length of b.
