Home > Archives > 2007年03月23日

2007年03月23日

Bracket Matching @sed

正規表現によるマッチング回数を減らし，正規表現の単純化もすることで TLE を克服．当初 142B だったが C言語に抜かれたのでプログラムを直し現在 117B まで縮んだ．

とりあえず，正規表現の処理スピードとしては

/^\(AB\|CD\|EF\|GH\)/

より

/^AB\|^CD\|^EF\|^GH/

のほうが速いらしい．

あと，

s/fuga/hoge/

と

/fuga/s//hoge/

だと後者のほうが遅い．二回マッチングを取っているみたい．条件部分でのマッチングと同じだからマッチング結果を使いまわしてほしいなぁ．

ここらが合わさると，

/^\(AB\|CD\|EF\|GH\)/{s///;b1}

では timeout だけど

/^\(AB\|CD\|EF\|GH\)/{s/..//;b1}

だと大丈夫などの現象が生じるらしい．

Home > Archives > 2007年03月23日

Search

Feeds

Page Top