找到沒有特定子串的字符串的編號

Question

問題給出N（1 < = N < = 10）長度不超過6的字符串，我如何計算長度爲L的字符串的數量（1 < = L < = 1000000 ）沒有任何n字符串作爲子字符串。 每個字符串只包含大寫字母。

最好的我能想到的是使用dp L *（26^5），但我不認爲這會超過時間限制:(任何人都可以分享一些想法？btw這裏的原始問題http://www.spoj.com/problems/GEN/如果你不明白我上面寫

Answer 1

首先，創建一個接受所有的「壞」的字符串，然後它用子集構造轉換爲DFA的NFA（非確定性有限自動機），然後計算該DFA的補充。

計算DFA接受的字符串的數量是相當直接的;在給定狀態下結束的長度爲k + 1的字符串的數量可以通過將在每個預定中結束的長度爲k的字符串的數目相加來計算索爾州。

如果你有一個體面的實施，這可能會及時運行。但是，如果沒有，則可以使用Aho-Corasick預處理中的自動機來代替DFA。