Description:
N語からなる禁止語リストとM個のクエリが与えられる。(0<=N<=1000, 1<=M<=100, 禁止語は1文字～3文字の単語)
a b c ... z aa ab ... az ba bb ... zz aaa ....
というようなに単語列から、禁止語を部分文字列に含んでいる物を全部取り除く。
クエリが単語なら、この単語列の何番目に存在するかを答え、
クエリが数字なら、その位置の単語を答えよ。
入力/出力の単語は20文字を超えず、数字は20億を超えない。
Answer:
予め、どの3文字が来たら駄目かを意味する3次元配列を作り、1000個との比較を行わなくても良いようにしておく。
その後、ある2文字に続くある長さの文字列がいくつ存在するかでDPを行う。(27*27*21)
このテーブルを用いると、番号が与えられた時に単語を答える事ができる。
単語が与えられた時は、番号->単語の関数をバイナリサーチを行うと、コーディングが楽になる。
Source: