エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Spaghetti Source - 複数パターン検索 (Aho-Corasick)
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Spaghetti Source - 複数パターン検索 (Aho-Corasick)
説明 複数のパターン文字列からなる集合と長い文字列が与えられる.長い文字列に対してマッチするパター... 説明 複数のパターン文字列からなる集合と長い文字列が与えられる.長い文字列に対してマッチするパターン文字列をすべて求めるアルゴリズムが Aho Corasick である.これは複数パターン文字列をあらかじめ trie に変換してから KMP を実行し,パターンマッチング・オートマトンを構成していることになる. 詳しくは適当な成書や http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf などを参考のこと. 計算量 構築 O(m). 検索 O(n + m). ただし m はパターンの文字列長の総和,n は検索テキスト長. 使い方 struct PMA; を適宜設定のこと. buildPMA(char *p[], int m) 0 ... m-1 の複数の検索パターンから,パターンマッチング・オートマトンを構築する. match(c