正規表現の暴走：破滅的バックトラック
(a+)+$ のような式に aaaa…! を食わせると、マッチ試行が指数爆発する。これが ReDoS（正規表現サービス妨害）の正体です。
多くの言語の正規表現エンジンはバックトラック型です。「できるだけ多く飲み込む（貪欲）→ 失敗したら 1 文字戻してやり直す」を繰り返します。
(a+)+ のように入れ子の量指定子があると、試行回数は文字数 n に対して 2ⁿ 級で増えます。
正規表現パターン（教科書的な ReDoS パターン）
12
あり
調べる入力文字列
試行回数（ステップ）
—
結果
—
理論オーダー
—
推定実時間 @10M/s
—
いま何が起きている？
試行回数 vs n（縦軸は対数）
バックトラック試行ツリー（青=前進 / 赤=失敗して戻る）
ここがポイント
- 入れ子の量指定子が地雷 ──
(a+)+(a*)*(a|a)*は同じ並びを分割し直す組み合わせが指数的。 - 最後に「必ず失敗する 1 文字」を置くと、全分割を試し尽くすまで終わらない（
!を外すと即マッチで爆発しない）。 - n を 1 増やすだけで試行回数はほぼ倍 ── 2ⁿ なので 30 文字程度でも億単位、現実のサーバが固まる。
- 対策 ── 入れ子量指定子を避ける／
a+等に書き換える／RE2 など線形時間エンジン（バックトラックしない）を使う。