Struct nekolib::seq::kmp::KmpSearcher

source ·
pub struct KmpSearcher<T: Eq> { /* private fields */ }
Expand description

KMP 法 (Knuth–Morris–Pratt algorithm)。

文字列 $S$ を入力とする。 各 $S[\dots i]$ ($0\le i\le |S|$) の最長 border と最長 tagged border の長さを求める。該当する border が存在しない要素は $-1$ とする。

文字列 $S[\dots i]$ の border とは、$S[\dots i]$ の真部分文字列であり、$S[\dots i]$ の接頭辞かつ接尾辞であるような文字列である。

文字列 $S[\dots i]$ の border $S[\dots j]$ ($0\le j < i$) が $S[j] \neq S[i]$ を満たすとき、$S[\dots j]$ は $S[\dots i]$ の tagged border (strict border, strong border) であると言う。ただし、$S[|S|]$ は $S$ 中に含まれない文字として定義する。

    0 1 2 3 4 5 6 7 8   9 ...
  +-------------------+-------+
S | a a b a c a a b a | c ... |
  +-------------------+-------+

この例において、$S[\dots 4] = \mathtt{aaba}$ は $S[\dots 9] = \mathtt{aabacaaba}$ の border だが tagged border ではない ($S[4] = S[9] = \mathtt{c}$)。一方、 $S[\dots 2] = \mathtt{aa}$ は tagged border である ($S[2] = \mathtt{b} \neq S[9] = \mathtt{c}$)。

この tagged border を用いることで、パターン検索を高速に行う。

Idea

tagged border を $O(|S|)$ 時間で求める方法と、パターン検索を $O(|T|)$ 時間で行う方法について書く。

Implementation notes

パターンが静的な場合であれば最長 border を求める必要はない。 パターンの末尾に対する push のみを考慮する場合も同様のはず。 ここではパターンの末尾に対する pop を行える実装になっており、その更新の際には最長 border の長さが必要になるはず。

Complexity

構築は $O(|S|)$ 時間。パターン末尾における更新は $O(\log(|S|))$ 時間。 ただし、末尾への追加はこれに worst $O(|S|)$ (amortized $O(1)$) 時間が加わる。

References

  • Knuth, D. E., Morris, Jr, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM journal on computing, 6(2), 323-350.

See also

Implementations§

source§

impl<T: Eq> KmpSearcher<T>

source

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

Trait Implementations§

source§

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

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

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

source§

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

Formats the value using the given formatter. Read more
source§

impl<T: Eq> From<Vec<T, Global>> for KmpSearcher<T>

source§

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

Converts to this type from the input type.
source§

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

source§

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

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

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.
source§

impl<T: Eq> PopBack for KmpSearcher<T>

§

type Output = usize

source§

fn pop_back(&mut self) -> Option<usize>

source§

impl<T: Eq> PushBack for KmpSearcher<T>

§

type Input = T

source§

fn push_back(&mut self, x: T)

source§

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

source§

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

source§

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

Auto Trait Implementations§

§

impl<T> RefUnwindSafe for KmpSearcher<T>where T: RefUnwindSafe,

§

impl<T> Send for KmpSearcher<T>where T: Send,

§

impl<T> Sync for KmpSearcher<T>where T: Sync,

§

impl<T> Unpin for KmpSearcher<T>where T: Unpin,

§

impl<T> UnwindSafe for KmpSearcher<T>where T: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for Twhere V: MultiLane<T>,

§

fn vzip(self) -> V