问题是给定长度不超过6的N（1 <= N <= 10）字符串，我如何计算长度为L（1 <= L <= 1000000）的字符串数，而没有任何n个字符串作为子字符串. 每个字符串只包含大写字母。
我能想到的最好的方法是使用 dp L * (26^5) 但我认为这不会超过时间限制 :( 任何人都可以分享一些想法吗？顺便说一句，这是最初的问题http://www.spoj.com/问题/GEN/如果你不明白我上面写的
问问题
906 次
1 回答
3
首先，创建一个接受所有“坏”字符串的 NFA（非确定性有限自动机）。然后使用子集构造将其转换为 DFA。然后计算该 DFA 的补码。
计算 DFA 接受的字符串数量相当简单；以给定状态结束的长度为 k+1 的字符串的数量可以通过将在每个前导状态结束的长度为 k 的字符串的数量相加来计算。
如果你有一个体面的实现，这可能会及时运行。但是，如果没有，您可以使用Aho-Corasick预处理中的自动机而不是 DFA。
于 2013-04-21T07:24:20.690 回答