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