問題は、長さが6以下のN（1 <= N <= 10）文字列が与えられた場合、部分文字列としてn文字列を使用せずに、長さL（1 <= L <= 1000000）の文字列の数を計算するにはどうすればよいですか. すべての文字列には大文字のみが含まれます。
私が考えることができる最善の方法は dp L * (26^5) を使用することですが、これで制限時間を超えるとは思いません:( 誰かアイデアを共有できますか?ところで、元の問題http://www.spoj.com/問題/GEN/上記の内容が理解できない場合
まず、「悪い」文字列をすべて受け入れる NFA (非決定性有限オートマトン) を作成します。次に、サブセット構築を使用して DFA に変換します。次に、その DFA の補数を計算します。
DFA によって受け入れられる文字列の数をカウントするのはかなり簡単です。特定の状態で終わる長さ k+1 の文字列の数は、各先行状態で終わる長さ k の文字列の数を合計することによって計算できます。
まともな実装があれば、これはおそらく間に合うでしょう。ただし、そうでない場合は、DFA の代わりにAho-Corasick前処理のオートマトンを使用できます。