From: Tanaka Akira <akr@...17n.org>
Date: 2003-05-19T17:34:56+09:00
Subject: [ruby-dev:20216] Re: /()*\1/ =~ ""

In article <5FD2F0CF7F5D7F44B00F36870B9E78B508DE5024@SBG-EX4>,
  kkosako@softbank.co.jp writes:

> こういう場合があるんですね。考えていませんでした。
> 選択肢の数だけの繰り返しは、必ず試すように変更すれば良いような気がしますが、
> それだけでどのようなパターンにも対応できるのか、わかりません。
> 誰か教えてください。
>
> 対処方法があっても、速度的な不利が大きすぎる場合は
> 放置するかもしれませんが。

backreference が入ると NP 完全になるので、もし効率良くできたら世界的に
有名になれるんじゃないですかね。
http://perl.plover.com/NPC/

さて、とすると、

(1) 指数関数的な時間を使って全部解く
(2) 適当にあきらめる

という選択肢があるわけですが、もし (2) をとるなら、どういうようにあき
らめるかが問題になります。あきらめかたをいかにわかりやすくするかという
か。

なんとなく、根拠はないんですが、繰り返しの中身は空文字列にマッチしない、
というのがいいかなぁ、と思い始めて来たんですが、どんなもんでしょう?
-- 
[田中 哲][たなか あきら][Tanaka Akira]