如何在&[u8]切片中找到子序列？

Question

我&[u8]在二进制缓冲区上有一个切片.我需要解析它,但是我想要使用的很多方法(例如str::find)在切片上似乎不可用.

我已经看到我可以通过使用缓冲切片和我的模式来转换它str,from_utf8_unchecked()但这似乎有点危险(而且也非常hacky).

如何在此切片中找到子序列？我实际上需要模式的索引,而不仅仅是部件的切片视图,所以我认为split不会起作用.

Answer 1

这是一个基于windows迭代器的简单实现.

fn find_subsequence(haystack: &[u8], needle: &[u8]) -> Option<usize> {
    haystack.windows(needle.len()).position(|window| window == needle)
}

fn main() {
    assert_eq!(find_subsequence(b"qwertyuiop", b"tyu"), Some(4));
    assert_eq!(find_subsequence(b"qwertyuiop", b"asd"), None);
}

该find_subsequence函数也可以是通用的:

fn find_subsequence<T>(haystack: &[T], needle: &[T]) -> Option<usize>
    where for<'a> &'a [T]: PartialEq
{
    haystack.windows(needle.len()).position(|window| window == needle)
}

Answer 2

我认为标准库不包含此功能。一些 libc 有memmem，但目前 libc 箱没有包装它。不过，您可以使用twoway板条箱。rust-bio也实现了一些模式匹配算法。所有这些都应该比使用更快haystack.windows(..).position(..)