やったこと

ReDoS

昨日から後方参照の展開の繰り返しの量指定子の対応を完成させた。
紆余曲折あったけど実装しきれたので良き。

ちなみに (x|y)+\1 は今のところ (x|y)+xx|(x|y)+yy|xx|yy と展開される。
どうして (x|y)*xx|(x|y)*yy じゃないのかというと、+ の中身に空文字列(先読みとか)が含まれている場合のため。
例えば (x|y|(?=x))+\1 を考えると、繰り返しの省略可能部分は空文字列を含まないので (x|y|(?=x))*xx|(x|y|(?=x))*yy|(x|y|(?=x))*(?=x) のようには展開できなくて、(x|y|(?=x))+xx|(x|y|(?=x))+yy|xx|yy|(?=x) とするのが正しいからだったりする。
とはいえ繰り返しの中身が明らかに空文字列を含まないなら (x|y)*xx|(x|y)*yy でもいいはずなので、可能ならそういう風に展開できるようにしたい気もする。

スタマス

時間が取れたのでスタマスやってた。
5月の途中まで。
時間かかるなぁ、というのと、油断するとステージの攻略に大分時間がかかるのがつらい。
がんばろう。