[AHOI2005]病毒检测

[AHOI2005]病毒检测
这个可以给出O(n^3)复杂度的代码,肯定就是O(n^3)啦,没有质疑的空间了。那么有什么代码开一跑怎么快呢,DP,DFS,贪心。
这里的话我们就用DP解一下这题
F[i][j]代表母串匹配i个,字串匹配到j个时可不可以匹配到。
然后更新一下,注意*要特判一下,因为他可以匹配很多个字符。

发表评论

电子邮件地址不会被公开。 必填项已用*标注