RE / NFAとDFAを読んだ後、文字列内の部分文字列の検索は、ブルートフォースO（mn）検索ではなく、REを使用すると実際には漸近的に高速になる可能性があります。私の推論は、DFAが実際に状態を維持し、「干し草の山」内の各文字を複数回処理することを回避するということです。したがって、長い文字列での検索は、正規表現を使用すると実際にははるかに高速になる可能性があります。
もちろん、これはNFAからDFAに変換するREマッチャーにのみ有効です。
ブルートフォースマッチャーではなくREを使用した場合、実際にストリングマッチのパフォーマンスが向上した人はいますか？
まず、いくつかの言語での正規表現の内部に関する記事を読むことをお勧めします。正規表現のマッチングは単純で高速です。
多くの言語の正規表現は照合用であるだけでなく、グループキャプチャと逆参照の可能性も提供するため、ほとんどすべての実装では、特定の正規表現から構築されたNFAを実行するときに、いわゆる「バックトラッキング」を使用します。そして、この実装には指数関数的な時間計算量があります（最悪の場合）。
DFA（グループキャプチャを使用）を介してREを実装することもできますが、オーバーヘッドがあります（Laurikariの論文「タグ付き遷移を使用したNFA、決定性オートマトンへの変換、および正規表現への適用」を参照）。
単純な部分文字列検索の場合、DFAを構築して部分文字列を検索するKnuth-Morris-Prattアルゴリズムを使用できます。これは、最適なO（len（s））の複雑さを備えています。ただし、オーバーヘッドもあります。実際の単語やフレーズ（それほど反復的ではない）でこの最適なアルゴリズムに対してナイーブアプローチ（O（nm））をテストすると、平均してナイーブアプローチの方が優れていることがわかります。
正確な部分文字列検索については、ボイヤー-ムーア文字を試すこともできます。これは、O（mn）の最悪の場合の複雑さを持ちますが、実際のデータでは平均してKMPよりもうまく機能します。
実際に使用されるほとんどの正規表現はPCRE（Perl-Compatible Regular Expressions）です。これは正規言語よりも幅が広いため、正規文法では表現できません。PCREには、正/負の先読み/後読みアサーション、さらには再帰などがあるため、解析では一部の文字を複数回処理する必要がある場合があります。確かに、それはすべて特定のREの実装に帰着します。つまり、式が正規文法の範囲内にとどまる場合に最適化されるかどうかです。
個人的には、この2つのパフォーマンスを比較したことはありません。ただし、私の経験では、ブルートフォースの検索と置換でパフォーマンスの問題が発生したことは一度もありませんでしたが、REのパフォーマンスのボトルネックに何度も対処する必要がありました。
ほとんどの言語のドキュメントを見ると、正規表現を使用する必要がない場合は、パフォーマンス上の理由から非正規表現バージョンを使用する必要があると記載されています...例：http ：//www.php.net/manual/en/ function.preg-split.phpは次のように述べています。「正規表現の力が必要ない場合は、explode（）やstr_split（）などのより高速な（単純ではありますが）代替手段を選択できます。」
これは、どこにでも存在するトレードオフです。つまり、より柔軟で機能が豊富なソリューションは、パフォーマンスが低下します。