指数関数的発散(10) コメントの返事

時間コストについては、実際に実装してみるしかないでしょうか。
初期化を何回実行するかは、パターンと入力文字列に依存するので、簡単なテストでは分からないですね。
(それにしても、Perlは本当にこういう処理をしているのか？)
記憶領域を節約するために、飛び飛びの文字列位置を記録する方法は、停止性が完全には保障されなくなりませんか？尤も、後方参照があるときに適用できないので、保証する必要もないかもしれませんが。