<p>我确信有不同的方法来实现这一点,我将使用<a href="http://en.wikipedia.org/wiki/Merge_algorithm" rel="nofollow">merge</a>算法遍历这两个数组,跟踪重叠区域。如果您不熟悉这个概念,请看一下<a href="http://en.wikipedia.org/wiki/Merge_sort" rel="nofollow">merge-sort</a>,希望在它和代码之间可以清楚地看到它是如何工作的。在</p>
<pre><code>def find_overlap(a, b):
i = 0
j = 0
len_a = len(a)
len_b = len(b)
in_overlap = False
best_count = 0
best_start = (-1, -1)
best_end = (-1, -1)
while i < len_a and j < len_b:
if a[i] == b[j]:
if in_overlap:
# Keep track of the length of the overlapping region
count += 1
else:
# This is a new overlapping region, set count to 1 record start
in_overlap = True
count = 1
start = (i, j)
# Step indicies
i += 1
j += 1
end = (i, j)
if count > best_count:
# Is this the longest overlapping region so far?
best_count = count
best_start = start
best_end = end
# If not in a an overlapping region, only step one index
elif a[i] < b[j]:
in_overlap = False
i += 1
elif b[j] < a[i]:
in_overlap = False
j += 1
else:
# This should never happen
raise
# End of loop
return best_start, best_end
</code></pre>
<p>注意,end here在python约定中返回,因此如果<code>a=[0, 1, 2]</code>和{<cd2>},<code>start=(0, 0)</code>和{<cd4>}。在</p>