TaylorSwift13
2023-09-14 20:41 广州城市职业学院 Java
关注
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
相关推荐
点赞 评论 收藏
分享
投递美团等公司6个岗位 
⑨✌们拿它练练面试愣是给他整出幻觉了 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 写给毕业5年后的自己 #
5064次浏览 105人参与
# 国央企笔面经互助 #
129912次浏览 1082人参与
# 华泰证券Fintech星战营 #
169423次浏览 196人参与
# 职场捅娄子大赛 #
324027次浏览 3297人参与
# 好好告别我的学生时代 #
48804次浏览 907人参与
# 一人一个landing小技巧 #
61241次浏览 972人参与
# 毕业季等于分手季吗 #
17728次浏览 224人参与
# 美的求职进展汇总 #
274795次浏览 1955人参与
# 海信求职进展汇总 #
65363次浏览 361人参与
# 晒一下我的毕业照 #
35188次浏览 398人参与
# 毕业后不工作的日子里我在做什么 #
172141次浏览 1521人参与
# 记录实习开销 #
31301次浏览 213人参与
# 如何缓解求职过程中的焦虑？ #
8268次浏览 106人参与
# HR问：你期望的薪资是多少？如何回答 #
40389次浏览 527人参与
# 如果今天是你的last day，你会怎么度过？ #
22992次浏览 199人参与
# 大学最后一个寒假，我想…… #
38443次浏览 500人参与
# 毕业租房也有小确幸 #
110224次浏览 4327人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
108570次浏览 783人参与
# 视觉/交互/设计百问百答 #
43353次浏览 428人参与
# 2022毕业即失业取暖地 #
97159次浏览 651人参与
# 材料转码还有必要吗？ #
22010次浏览 135人参与