[解決済み] 正規表現の複雑さとは？

質問

文字列の正規表現比較を実行するために必要な、文字列長に対する複雑さは何ですか？

どのように解決するのですか？

答えは、「正規表現」が何を意味しているかによります。 コンパイルされた に 決定論的有限オートマトン という長さの文字列にマッチする N で O(N) の時間です。正規表現言語に対するある種の拡張は、それを悪い方向に変えてしまいます。

以下のドキュメントが参考になると思います。 正規表現マッチングはシンプルで高速にできる .