needle

用 Rust 编写的搜索算法

支持 Boyer-Moore 和 BM-Horspool，可以用于任何 Copy 类型的数组搜索，有一些限制。

当你只需要在字节中进行搜索，而不需要特别考虑 Unicode 字符时，此实现通常比 Rust 标准库中的 &str::find() 快速。

示例

BoyerMoore 和 Horspool 的接口基本上是相同的。以下示例使用 Boyer-Moore 在文本中查找所有 "Peter Piper" 实例。

use needle::BoyerMoore;
let haystack = b"Peter Piper picked a peck of pickled peppers.\
                 A peck of pickled peppers Peter Piper picked.\
                 If Peter Piper picked a peck of pickled peppers,\
                 Where's the peck of pickled peppers Peter Piper picked?";
let needle = BoyerMoore::new(&b"Peter Piper"[..]);
for i in needle.find_in(haystack) {
    println!("Found Peter Piper at index {}.", i);
}

一般来说，字节搜索是最快的。但如果你方便，也可以搜索其他字母表。例如

use needle::Horspool;

#[derive(Copy, Clone, Debug, PartialEq)]
enum Nucleotide {
    A, T, C, G
}

// An Into<usize> impl is required for the search alphabet
impl Into<usize> for Nucleotide {
    #[inline]
    fn into(self) -> usize { self as usize }
}

// Convenience to create an RNA chain from a string representation
fn from_str(other: &[u8]) -> Vec<Nucleotide> {
    other.into_iter().map( |&c| {
        match c.into() {
            b'A' => Nucleotide::A,
            b'T' => Nucleotide::T,
            b'C' => Nucleotide::C,
            b'G' => Nucleotide::G,
            _ => panic!("Unknown nucleotide {:?}", &c),
        }
    }).collect()
}

fn main() {
    let haystack = from_str(b"ACCTGATCGGGTGGTACACGATAATATCGTGGCATGCACTTGCTGATCGCTTAGACTGCAAAATCGTAGCCAGTAGGT");
    let haystack = haystack.as_slice();
    let subsequence = &[Nucleotide::C, Nucleotide::G, Nucleotide::C, Nucleotide::T][..];
    let needle = Horspool::new(subsequence);
    assert!(needle.find_first_in(haystack).is_some());
}