rust-lang / regexは線形時間で正規表現のマッチが出来るらしい - matsu7874のブログ

この記事は Rust Advent Calendar 2022 1日目の記事です。 正規表現によるパターンマッチについて、ナイーブな深さ優先探索による正規表現のマッチを考えるとパターンの複雑さによって計算時間が大幅に変化しそうです。例えば文字列 aaaaaaaa がパターン (aa|a)+b にマッチしないことを確かめる方がパターン a+b にマッチしないことを確かめるよりも時間がかかりそうです。 すべての"a"は一文字の"a"でしか使われない "aa"で使われる場合と"a"で使われる場合があるため経路数が多い しかし、Rustの正規表現モジュールregexはパターンによらず線形時間で探索が可能だと言っています。 all searches execute in linear time with respect to the size of the regular expression an