首页 > 其他 > 详细

一类巧妙利用利用失配树的序列DP

时间:2020-10-18 22:46:57      阅读:48      评论:0      收藏:0      [点我收藏+]

I.导入

求长度为\(\text{len}\)的包含给定连续子串\(\text{T}\)的 0/1 串的个数。(\(|T|<=15\))

通常来说这种题目应该立刻联想到状压 DP 与取反集——这样就不用考虑大量重复情况的容斥问题。设\(f_{i,S}\)表示前\(i\)个字符、最后\(|T|\)个字符为\(S\)、不包含给定连续子串的情况数,状态转移方程简单不述。时间复杂度 \(\Theta(2^{|T|}\text{len})\)

II.巧妙利用利用失配树的序列DP

上述算法的时间复杂度相当高昂,当\(\text{T}\)十分大或者不是一个 0/1 串而是一个字符串的时候完全不可做,并且大量的状态是无用的,因为我只关心不出现给定的字符串,然而相当多的状态不用转移已经注定了不可能出现给定字符串,用状态压缩表示表示整段的完整状态非常亏本。重磅的优化来了:

我们在 DP 状态的设置上模拟 KMP 算法的过程。设\(f_{i,j}\)表示前\(i\)个字母、已经匹配到了模式串的\(j\)时有多少种情况。那么状态转移也依照 KMP 算法:枚举当前点的\(j\)并枚举下一个点填的字符,在失配树上找到下一个点的\(j\),把\(f\)累加过去,时间复杂度\(\Theta(\text{len}|T|^2s)\),其中\(s\)是字符种类数。

当然不止可以在模式串上加强,还可以在文本串上加强:当\(\text{len}\)是天文数字的时候,我们完全可以用矩阵快速幂优化上述过程,时间复杂度是\(log\)的。

III.例一:诗人小\(K\)

技术分享图片

一类巧妙利用利用失配树的序列DP

原文:https://www.cnblogs.com/Linshey/p/13836918.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!