オンサイトで未確認

ukuku09の活動記録。

UVALive 7724 - Regular Number

思いつけばそれほど難しくないと思う。

問題概要

長さ $N$ の数字列にマッチする正規表現と長さ $5*10^6$ 以下の数字列が与えられる。正規表現にマッチする数字列の部分列を左から順に答えよ。

考察

$N+1$ 個の状態を一列に並べたオートマトンを考える。$i$($0 \le i \le N$) 文字マッチしているのをオートマトンの状態 $i$ にいると考えると、$j$($1 \le j \le N$)文字目の正規表現は状態 $j-1$ から状態 $j$ に進めるかどうかを決めるラベルとなる。

各数字についてどこにラベルがあるかと今のオートマトンの状態をbitsetで管理してやると、ビットアンドとビットシフトを組み合わせて始点の異なる複数の部分列のマッチング状態を一度に扱うことができる。

gist4297e823efc52ece391983f11374e1ad