Aho-Corasick法による複数文字列(パターン)検索を試す - Negative/Positive Thinkingはじめに Rabin-Karp法による複数文字列検索に続いて、同様に複数の文字列検索を行えるAC法を試しに書いてみた。 AhoCorasick法 えいほこらしっくほう 文字列探索するときに、パターンマッチオートマトン(PMA)を使い、状態を遷移させながらO(n)でパターンマッチを行う方法 入力文字列を一文字ずつ読み込みながらPMAの状態を遷移 PMAは与えられるパターンを表現する ノードは状態、辺は対応する文字、を表す PMA構築アルゴリズムは、 パターン文字列のTrieを作成 根から幅優先探索で各ノードで遷移が失敗した場合の遷移先を決定 そこへ辺を張る、を繰り返す 失敗時の遷移先の決定 trieと違って、葉ノードまでたどりきったら終了ではなく、失敗したときに遷移するノードを決めておくことで、連続して探索を行える (図1) パターン文字列「ab」と「bcd」に対して、入力「abcde」を考
TechCrunch | Startup and Technology News
手で大きさを示せば、その長さを自動計測して検索できる「空間検索」を発明しました～AR三兄弟のライフハックシリーズ vol.3 | ライフハッカー・ジャパン
