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

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) space 算法只是让您将任一序列的每个元素一起比较，以跟踪距序列开头的距离的最小差异。

O(n log n) 时间 O(n) space 算法仅对序列进行排序并进行比较，同时保持对 smallest/largest 元素的跟踪。

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

Answer 1

一个选项是构建一个 table 大小为 |Σ| 的系统，其中 Σ 是您的字母表，它将每个符号与其在字符串 x 中占据的第一个位置相关联。然后，您可以遍历 x，并针对每个字符，在 table 中记录该字符在 x 中的第一个位置。然后，您可以遍历字符串 y，对于 y 的每个字符，查询 table 以查找该字符第一次出现在字符串 x 中的时间。你没有在你的问题中提到你是如何定义 "smallest" 对的（字典顺序？最小化 i + j？其他的？），但你应该能够生成所有可能的对，然后取最小的他们在线性时间内。

总的来说，这需要时间 O(n + |Σ|) 并使用 space O(|Σ|)，所以如果您的字母表不是太大，这会非常快。如果您的字母表很大，只需使用散列 table ，最终预计 O(n) 时间为 O(n) space.

Answer 2

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

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

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

伪代码：

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) 边界，但没有想到证据。

Answer 3

O(n+m) 算法：

从 i = 0 和 j = 0 开始
如果 x[i] < y[j] i++
如果 x[i] > y[j] j++
如果 x[i] == y[j] => 你找到了

显然您还需要检查数组边界。

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

Find first element match between two sequences in linear time?

string

algorithm

big-o

time-complexity