T2 区间子串数量 刚看到题还以为是KMP吓一跳,一看范围那没事了。据样例可知问的是连续子串,还可以重叠,那么直接用前缀和处理即可,记录截止到当前字符串的子串数量,每次查询只需要将左右边缘前缀和相减。 注意左边缘不是l-1, 而是l-1+(m-1)。比如abcabc匹配abc的前缀数组是0001112,l=1, r=6(即bcabc)时,答案计算是2-1而不是2-0(第一个abc不是整个在区间内的)。 时间复杂度O(m*n),空间复杂度O(n)
1 1

相关推荐

拿到了ssp的小鲸鱼...:满分160做90+是吧
投递中国电信等公司10个岗位
点赞 评论 收藏
分享
未知的命运:大佬这都找不到我还找啥啊
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务