Struct nekolib::seq::ZSearcher

pub struct ZSearcher<T: Eq> { /* private fields */ }

Z algorithm。

文字列 $S$ について、$Z[i]$ ($0\le i < |S|$) が $S$ と $S[i\dots]$ の最長共通接頭辞の長さであるような配列 $Z$ を構築する。

Implementation notes

テキスト T 中のパターン P を探すとき、T と P に含まれない文字 '$' を用いて作った文字列 P + '$' + T の Z value を計算することで求められる。

一方、この方法においては '$' を適切に探す必要がある。 caller 側が探すのは面倒・バグの元であり、callee 側が探すのはコストがかかる。 あるいは、そういう元が存在しない場合もなくはない。

さて、P + '$' + T を読み込んだ場合の挙動は '$' を仮定しなくても模倣できる。 よって、多少の実装量には目をつぶりつつそういう実装にした。 テキストがパターン構築時には与えられないような場合や、 複数の処理がオンラインに与えられる場合にも対応しやすいと思う。

Suggestions

std::str::matches の実装を参考にするなどして、fn occurrences(&self) を持つような trait を作るとよさそう。テストを KMP に対して再利用できるので。

Complexity

構築は $O(|S|)$ 時間。検索は、テキスト $T$ に対して $O(|T|)$ 時間。

Implementations

impl<T: Eq> ZSearcher<T>

pub fn occurrences<'a>(&'a self, s: &'a [T]) -> Occurrences<'a, T>

pub fn z(&self, i: usize) -> usize

Trait Implementations

impl<T: Clone + Eq> Clone for ZSearcher<T>

fn clone(&self) -> ZSearcher<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Eq> Debug for ZSearcher<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Clone + Eq> From<Vec<T, Global>> for ZSearcher<T>

fn from(pat: Vec<T>) -> Self

Converts to this type from the input type.

impl<T: PartialEq + Eq> PartialEq<ZSearcher<T>> for ZSearcher<T>

fn eq(&self, other: &ZSearcher<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq + Eq> Eq for ZSearcher<T>

impl<T: Eq> StructuralEq for ZSearcher<T>

impl<T: Eq> StructuralPartialEq for ZSearcher<T>