我很新,希望这不是太明显,但似乎找不到以下问题的简短而精确的答案。
我有两个列表:
a = [2,3,5,2,5,6,7,2]
b = [2,5,6]
我想找到第二个列表(
b
)中所有索引都在第一个列表(a
)中的时候,得到类似这样的结果:
b
在a
中的索引: 3, 4, 5
或者 b = a[3:6]
使用列表推导:
>>> [(i, i+len(b)) for i in range(len(a)) if a[i:i+len(b)] == b]
[(3, 6)]
或者使用 for 循环:
>>> indexes = []
>>> for i in range(len(a)):
... if a[i:i+len(b)] == b:
... indexes.append((i, i+len(b)))
...
>>> indexes
[(3, 6)]
此外,为了提高效率,您可以使用在字符串匹配中使用的KMP算法(来自这里):
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)
这将在a
中查找b
的第一个索引。因此,范围是搜索的结果,并加上b
的长度。
xrange(len(a))
,否则如果它在末尾,它将无法匹配序列。 - fraxel[(i, i+len(b)) for i in range(len(a)-len(b)+1) if a[i:i+len(b)] == b]
- new name