From: kkosako@...
Date: 2003-05-19T18:37:46+09:00
Subject: [ruby-dev:20218] Re: /()*\1/ =~ ""

> -----Original Message-----
> From: Tanaka Akira [mailto:akr@m17n.org]
> ...
> backreference が入ると NP 完全になるので、もし効率良くできたら世界的に
> 有名になれるんじゃないですかね。
> http://perl.plover.com/NPC/
> 
> さて、とすると、
> 
> (1) 指数関数的な時間を使って全部解く
> (2) 適当にあきらめる
> 
> という選択肢があるわけですが、もし (2) をとるなら、どういうようにあき
> らめるかが問題になります。あきらめかたをいかにわかりやすくするかという
> か。
> 
> なんとなく、根拠はないんですが、繰り返しの中身は空文字列にマッチしない
> 、
> というのがいいかなぁ、と思い始めて来たんですが、どんなもんでしょう?

その方向で良ければ、実装上もありがたい気がします。

無意味な例ですが、以下の場合もマッチしないということで納得して頂けますか？
/()*/ =~ ""
--
小迫＠出向中