knuth_morris_pratt
クラス · KMP法
template <class Container>
struct knuth_morris_pratt;
概要
KMP法
計算量
- pattern構築は $O(m)$、長さnの検索は $O(n+m)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
pattern tのfailure tableを構築する | $O(m)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
search |
検索 | $O(n+m)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator[] |
failure tableのi番目を返す | $O(1)$ |