在非可排序字母表中，常数空间、线性时间的一般字符串搜索。也称为精确字符串匹配。

在Rust术语中，这意味着我们可以定义以下函数

fn gs_find<T: Eq>(text: &[T], pattern: &[T]) -> Option<usize> {
    // ...
}

该函数以 O(n) 的时间和 O(1) 的空间进行计算。在最坏的情况下，此算法需要进行 4n 次字符比较。

请注意，如果字母表有线性顺序，Crochemore-Perrin（“双向”算法）要优越得多。

本作品的版权所有者是Ulrik Sverdrup "bluss"，请参阅包中的许可条款。

参考文献

这两篇论文都值得阅读。此crate实现中的注释也旨在解释和指出重要细节，因此也推荐阅读。

• [GS] Z. Galil和J. Seiferas，《时间-空间最优字符串匹配》，计算机与系统科学杂志（1983年）
• [CR] M. Crochemore和W. Rytter，《平方、立方和时间-空间高效的字符串搜索》，算法（1995年）