首页 > 单词
开通博客写题解
头像 范艺杰
发表于 2021-03-07 19:26:05
先用kmp求出t能出现在s的哪些位置。我们维护这样的三个dp方程：dp1[i]表示 最后一个区间结尾r在i的方案数。dp2[i]表示 最后一个区间结尾r在[0...i]的方案数。dp3[i]表示 最后一个区间开头l在[0...i]的方案数。转移即可，dp2[n]即为答案。复杂度O(n)。 #incl 展开全文
去ta的博客 赞 (5) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”