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

Question

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

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

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

1. 从vector_b映射创建哈希图value -> index
2. 迭代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)及时运行并且应该接近最快的实现——或者至少在同一个球场上。