Struct nekolib::seq::KmpSearcher

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

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

• https://snuke.hatenablog.com/entry/2014/12/01/235807
• https://snuke.hatenablog.com/entry/2017/07/18/101026
• https://potetisensei.hatenablog.com/entry/2017/07/10/174908
• http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

Implementations

impl<T: Eq> KmpSearcher<T>

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

Trait Implementations

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

fn clone(&self) -> KmpSearcher<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 KmpSearcher<T>

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

Formats the value using the given formatter.

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

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

Converts to this type from the input type.

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

fn eq(&self, other: &KmpSearcher<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> PopBack for KmpSearcher<T>

type Output = usize

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

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

type Input = T

fn push_back(&mut self, x: T)

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

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

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