algorithm - 如何检查向量是否是另一个向量的子序列(顺序相同但不连续)？

Question

如何检查 vector_a 的所有元素也以与 vector_b 相同的顺序出现?
vector_b可能很长，没有假设它已排序，但它没有重复的元素。

我找不到为 Vec 实现的方法或在 itertools 中，所以我尝试通过执行以下操作来实现:

从 vector_b 创建哈希图映射value -> index

迭代 vector_b并检查:

元素存在于哈希图中

索引严格大于前一个元素的索引

我对此并不满意，因为由于哈希图的创建，它的空间效率不高。

Answer 1

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

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) 时间运行并且应该接近最快的可能实现——或者至少在同一个球场上。