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
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC.html
