私は正規表現を使うのが初めてではないし、基本的なこれらが基づいている理論は有限状態機械です。
ただし、私はアルゴリズム分析があまり得意ではないので、正規表現が基本的な線形検索とどう比較されるのか理解できません。表面的には線形配列検索のように見えるので質問しています。(正規表現が単純な場合)
正規表現エンジンの実装について詳しく知るにはどこに行けばよいですか?
ベストアンサー1
これは最も人気のあるアウトラインの 1 つです。正規表現マッチングはシンプルかつ高速にDFA でコンパイルされた正規表現を文字列に対して実行すると、確かに O(n) ですが、最大 O(2^m) の構築時間/スペースが必要になる場合があります (m は正規表現のサイズ)。