关注
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
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 面试问题记录 #
32760次浏览 515人参与
# 入职第五天,你被拉进了几个工作群 #
14568次浏览 79人参与
# 京东TGT #
35845次浏览 157人参与
# 工作一周年分享 #
15519次浏览 103人参与
# 面试经验谈 #
21434次浏览 331人参与
# 面试吐槽bot #
5680次浏览 53人参与
# 机械人,你的第一份感谢信是谁给的 #
23638次浏览 295人参与
# 假如我穿越到了妈妈的18岁 #
2038次浏览 29人参与
# 零跑求职进展汇总 #
2326次浏览 16人参与
# 职场新人生存指南 #
339002次浏览 7261人参与
# 视觉/交互/设计招聘信息汇总 #
11076次浏览 596人参与
# 上班苦还是上学苦呢? #
215159次浏览 1288人参与
# 硬件人更看重稳定还是高薪 #
42328次浏览 213人参与
# 异地恋该为对方跳槽吗 #
27490次浏览 134人参与
# 机械求职避坑tips #
42698次浏览 356人参与
# 对妈妈没说出口的话 #
14153次浏览 341人参与
# 硬件人秋招的第一个offer #
67285次浏览 1083人参与
# 请用你的专业向妈妈表白 #
4544次浏览 48人参与
# 妈妈治愈了你哪些脆皮时刻 #
6331次浏览 112人参与
# 不考虑转正,实习多久合适 #
25965次浏览 119人参与
# 租房找室友 #
30620次浏览 150人参与