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
相关推荐
投递叮咚买菜等公司10个岗位 >
牛客热帖
正在热议
# 25届秋招总结 #
295065次浏览 2586人参与
# 如果不工作真的会快乐吗 #
58523次浏览 506人参与
# 阿里云管培生offer #
15572次浏览 289人参与
# 地方国企笔面经互助 #
3656次浏览 8人参与
# 美团求职进展汇总 #
1325589次浏览 12437人参与
# 选完offer后，你后悔学本专业吗 #
19151次浏览 139人参与
# 百度开奖 #
158027次浏览 946人参与
# 国央企薪资爆料 #
7025次浏览 52人参与
# 学历or实习经历，哪个更重要 #
50254次浏览 393人参与
# 正在实习的你，几点下班 #
51294次浏览 381人参与
# 米哈游求职进展汇总 #
175565次浏览 1456人参与
# 投递实习岗位前的准备 #
1178448次浏览 18386人参与
# 面试体验感最好的是哪家？ #
84861次浏览 842人参与
# 如何一边实习一边秋招 #
990991次浏览 12632人参与
# 得物求职进展汇总 #
66005次浏览 679人参与
# 求职遇到的搞笑事件 #
70467次浏览 575人参与
# 实习生应该准时下班吗 #
167260次浏览 1159人参与
# 网申一定要掌握的小技巧 #
5288次浏览 52人参与
# 0offer是寒冬太冷还是我太菜 #
897008次浏览 8003人参与
# 提前批简历挂麻了怎么办 #
146105次浏览 1942人参与
# 银行笔面经互助 #
82524次浏览 873人参与
# 腾讯求职进展汇总 #
195360次浏览 1637人参与