string - 在线性时间内找到两个序列之间的第一个元素匹配？

Question

假设我们有两个序列 x = {x_i : i elem [1,M]} 和 y = {y_i : i elem [1,N]} 具有有序的字母表。是否有可能找到最小的(如果有的话)对 (i, j) 使得 x_i = y_j？

简单的 O(n^2) 时间 O(1) 空间算法只是让您将任一序列的每个元素一起比较，以跟踪距序列开头的距离的最小差异。

O(n log n) 时间 O(n) 空间算法只是对序列进行排序和比较，同时保持跟踪最小/最大元素。

不过我想不出线性时间算法，我不确定这个问题会被称为什么。

Answer 1

首先，请注意它可以在 O(max{m,n}log(min{m,n})) 中完成，方法是仅对较小的列表进行排序，并在其上使用二进制搜索，同时迭代更大的列表。

此外，您可以使用哈希表将一个列表索引成对 x_i->min{j, x_j = x_i } - 这需要预期的线性时间和空间。
然后，简单地迭代另一个列表，并在表中查找y_i，同时保持目前找到的最小值。

这在平均情况下总计 O(n) 空间和时间。

伪代码:

table = {}
for each element x_i in x in ascending order of i:
  if x_i is not in table:
    table[x_i] = i
best_pair = (-1,-1)
for each element y_j in y:
  if y_j in table:
    if (table[y_j],j) is "better" than best_pair:
      best_pair = (table[y_j], j)
return best_pair

我很确定它与 element distinctness problem 太相似了在不使用散列的情况下克服 Omega(nlogn) 边界，但没有想到任何证据。