求长度为\(\text{len}\)的包含给定连续子串\(\text{T}\)的 0/1 串的个数。(\(|T|<=15\))
通常来说这种题目应该立刻联想到状压 DP 与取反集——这样就不用考虑大量重复情况的容斥问题。设\(f_{i,S}\)表示前\(i\)个字符、最后\(|T|\)个字符为\(S\)、不包含给定连续子串的情况数,状态转移方程简单不述。时间复杂度 \(\Theta(2^{|T|}\text{len})\)。
上述算法的时间复杂度相当高昂,当\(\text{T}\)十分大或者不是一个 0/1 串而是一个字符串的时候完全不可做,并且大量的状态是无用的,因为我只关心不出现给定的字符串,然而相当多的状态不用转移已经注定了不可能出现给定字符串,用状态压缩表示表示整段的完整状态非常亏本。重磅的优化来了:
我们在 DP 状态的设置上模拟 KMP 算法的过程。设\(f_{i,j}\)表示前\(i\)个字母、已经匹配到了模式串的\(j\)时有多少种情况。那么状态转移也依照 KMP 算法:枚举当前点的\(j\)并枚举下一个点填的字符,在失配树上找到下一个点的\(j\),把\(f\)累加过去,时间复杂度\(\Theta(\text{len}|T|^2s)\),其中\(s\)是字符种类数。
当然不止可以在模式串上加强,还可以在文本串上加强:当\(\text{len}\)是天文数字的时候,我们完全可以用矩阵快速幂优化上述过程,时间复杂度是\(log\)的。
原文:https://www.cnblogs.com/Linshey/p/13836918.html