Puzzle (UVa Live Archive Asia - Site 4 (Korea) - 2007/2008 Seoul (Korea))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3907

問題

Aから順番にn種類の文字が使えるパズルを行う。このパズルにはs種類の禁止ワードがある。前から順番に文字を出していき、禁止ワードを作らないように文字を並べていく。そうして作られる文字列の中で最長の物で、辞書順で最後の物を出力せよ。そのような文字列が無い場合、つまり、どの文字も使えない場合もしくは無限に長い文字列が作れる場合はNoと出力せよ。
1<=n<=26
1<=s<=1000

解法

Aho-Corasickっぽくパターンマッチングオートマトン作成し、そのグラフ上でメモ化dfsをする。dfsの最中に現在のdfsで既に探索した点を訪れた場合は無限に長くすることが可能。