Regular Expression Matching Can Be Simple And Fast
Regular Expression Matching Can Be Simple And Fastを読んで、Perlでの指数関数的発散の対処方法は、鬼車の実装方法と大体同じだろうということが分かった。
"Backtracking with memoization"と説明してあった。
ところで、この論文に書いてある例をPerlで実行すると、
("a" x 25) =~ /(?:a?){25}a{25}/;
確かに指数関数的に時間が掛かるが、次のように書き直すと、すぐに終了するようになる。
("a" x 25) =~ /(?:a?)*a{25}/;
Perlでは、繰り返し回数指定の場合には対処をしない仕様のようだが、実装上の都合だろうか。