如何使用另一个切片作为分隔符来拆分切片？

Question

标准库是否提供了一种使用另一个与待分割的同类型切片作为分隔符来分割切片的方法？标准库文档列出了基于单个元素分隔符的方法，而不是基于切片的方法。 例如：一个由5个u64整数组成的切片[1u64, 4u64, 0u64, 0u64, 8u64]使用[0u64, 0u64]作为分隔符进行分割，将会得到两个切片[1u64, 4u64]和[8u64]。

- Doe

Answer 1

截至Rust 1.9，标准库没有提供使用相同类型的另一个切片作为分隔符来分割切片[T]的方法，但您可以自己实现。

fn main() {
    let a = [1, 4, 7, 0, 0, 8, 10, 0, 0];
    let b = [0, 0];
    let mut iter = split_subsequence(&a, &b);
    assert_eq!(&[1, 4, 7], iter.next().unwrap());
    assert_eq!(&[8, 10], iter.next().unwrap());
    assert!(iter.next().unwrap().is_empty());
    assert_eq!(None, iter.next());
}

pub struct SplitSubsequence<'a, 'b, T: 'a + 'b> {
    slice: &'a [T],
    needle: &'b [T],
    ended: bool,
}

impl<'a, 'b, T: 'a + 'b + PartialEq> Iterator for SplitSubsequence<'a, 'b, T> {
    type Item = &'a [T];

    fn next(&mut self) -> Option<Self::Item> {
        if self.ended {
            None
        } else if self.slice.is_empty() {
            self.ended = true;
            Some(self.slice)
        } else if let Some(p) = self.slice
                                    .windows(self.needle.len())
                                    .position(|w| w == self.needle) {
            let item = &self.slice[..p];
            self.slice = &self.slice[p + self.needle.len()..];
            Some(item)
        } else {
            self.ended = true;
            let item = self.slice;
            self.slice = &self.slice[self.slice.len() - 1..];
            Some(item)
        }
    }
}

fn split_subsequence<'a, 'b, T>(slice: &'a [T], needle: &'b [T]) -> SplitSubsequence<'a, 'b, T>
    where T: 'a + 'b + PartialEq
{
    SplitSubsequence {
        slice: slice,
        needle: needle,
        ended: false,
    }
}

请注意，此实现使用朴素算法来查找相等的子序列。

- malbarbo

---

我相信，朴素算法的时间复杂度是O(n^2)，这也是它未被包含在标准库中的原因之一。 - Shepmaster

这就是我最终所做的。因为你花时间用实现来说明你的回答，所以给你加1分。 - Doe