如何检查一个向量是否是另一个向量的子序列（顺序相同但不连续）？

Question

如何检查vector_a的所有元素是否以与vector_b相同的顺序出现?

vector_b可能非常长，没有假设它已排序，但它没有重复元素。

我没有找到Vec或itertools中实现该方法，因此我尝试通过以下方式实现:

1. 从vector_b创建哈希映射将value->index映射
2. 遍历vector_b并检查:
   • 元素存在于哈希映射中
   • 索引严格大于前一个元素的索引

由于创建哈希映射不太空间有效，因此我对此并不满意。

- roynalnaruto

---

你可以在 vector_b 中简单地进行线性搜索，以查找 vector_a 的第一个元素。一旦找到它，就搜索下一个元素，以此类推。由于 vector_b 没有重复项，因此您永远不需要再次备份，所以这是 vector_b 长度的线性时间，并且只需要恒定的额外空间。 - Sven Marnach

一个简单的可能的优化是，一旦vector_a中剩余的元素比vector_b中的元素多，就退出循环，因为这时已经不可能找到所有的元素了。 - Sven Marnach

@PeterHall 元素是另一个从 Copy、Eq 和 PartialEq 派生的结构体。 - roynalnaruto

小澄清：给定 a = [1, 2] 和 b = [1, 0, 2]，算法应该返回 true 还是 false（b 是否包含与 a 相同顺序的相同元素）？或者 a 的元素是否应该在 b 中连续存在？ - Jmb

@Jmb 没错，它应该返回 true。连续性并非必需的。 - roynalnaruto

Answer 1

按顺序在干草堆中搜索needle的每个元素。每当找到匹配元素时，仅在剩余部分的干草堆中继续搜索。每次匹配元素时，可以通过取新的子切片来很好地表达这一点。

fn is_subsequence<T: PartialEq>(needle: &[T], mut haystack: &[T]) -> bool {
    for search in needle {
        if let Some(index) = haystack.iter().position(|el| search == el) {
            haystack = &haystack[index + 1..];
        } else {
            return false;
        }
    }
    true
}

assert!(is_subsequence(b"", b"0123456789"));
assert!(is_subsequence(b"0", b"0123456789"));
assert!(is_subsequence(b"059", b"0123456789"));
assert!(is_subsequence(b"345", b"0123456789"));
assert!(is_subsequence(b"0123456789", b"0123456789"));

assert!(!is_subsequence(b"335", b"0123456789"));
assert!(!is_subsequence(b"543", b"0123456789"));

切片只是一个指针和大小，存储在栈上，所以这不会进行新的分配。它运行的时间复杂度为 O(n) 并且应该接近于最快的实现 - 或者至少在同一范围内。

- Peter Hall

---

感谢清晰的解释。将haystack变为可变引用可能会有什么后果？我认为，如果这必须成为库的一部分，则允许不可变引用更为优选，对吗？ - roynalnaruto

@user2774555 haystack 不是可变引用。只有局部变量是可变的（它被重新分配为更小的子切片），但原始切片不能被改变：这需要参数为 haystack: &mut [T]。 - Peter Hall

Answer 2

最简单的方法是同时迭代这两个向量：

fn contains<T: PartialEq>(needle: &[T], haystack: &[T]) -> bool {
    let mut idx = 0;
    for it in needle {
        while (idx < haystack.len()) && (&haystack[idx] != it) {
            idx += 1;
        }
        if idx == haystack.len() {
            return false;
        }
    }
    return true;
}

- Jmb