How can I check if a vector is a subsequence (in the same order but not contiguous) of another vector?

Question

How can I check if all elements of vector_a also appear in the same order as vector_b?

vector_b could be very long, there is no assumption that it is sorted, but it does not have duplicate elements.

I could not find a method implemented for Vec or in itertools, so I tried implementing by doing:

1. Create a hashmap from vector_b mapping value -> index
2. Iterate over vector_b and check that:
   • Element exists in hashmap
   • Index is strictly greater than previous element's index

I am not really happy with this as it is not space efficient due to the creation of the hashmap.

Answer 1

Search for each element of the needle in the haystack in order. Each time you find a matching element, only continue the search in the remaining portion of the haystack. You can express this nicely by taking a new subslice of of the haystack each time you match an element.

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"));

A slice is just a pointer and a size, stored on the stack, so this does no new allocations. It runs in O(n) time and should be close to the fastest possible implementation - or at least in the same ballpark.

Answer 2

Easiest way to do it is to iterate the two vectors jointly:

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;
}