1063 shaares
28 private links
28 private links
8 results
tagged
regex
Thompson により提案されたオートマトンベースのアルゴリズムは、安定して高速に動作する。 backreference を導入したような拡張正規表現のためにバックトラックベースの正規表現エンジンを使っている言語は、特定の正規表現のマッチに指数的な時間が必要となるが、オートマトンベースであれば O(nm) (正規表現の長さと入力文字列の長さについて線形) で済む。
きわめて単純な C のソースコード付きでアルゴリズムを解説。
普通に NFA を実行するだけのシンプルなもの。そこそこ読みやすい。
続編: