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
相关推荐
查看19道真题和解析 10-29 22:30
吉林大学 Java 喵喵喵6_6：应该哪里不对吧，大厂都是20k以上的，10k那种对于985本的学生基本就是点击一下过了笔试就送的
，我前两天刚拿了一个11k，笔试完第2天就打电话了，非科班。坏消息是c++岗开这么低真是刷新认知了
，我前两天刚拿了一个11k，笔试完第2天就打电话了，非科班。坏消息是c++岗开这么低真是刷新认知了 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 校招生月薪1W算什么水平 #
36441次浏览 201人参与
# 一人一个landing小技巧 #
124405次浏览 1447人参与
# “vivo”个offer #
39659次浏览 282人参与
# 如果上班像打游戏，你最想解锁什么技能 #
8847次浏览 72人参与
# 我和mentor的爱恨情仇 #
76911次浏览 426人参与
# 为了实习逃课值吗？ #
29865次浏览 274人参与
# 工作后明白的那些道理 #
22241次浏览 225人参与
# 我是面试官，请用一句话让我破防 #
27480次浏览 130人参与
# 哪一瞬间觉得自己长大了 #
38760次浏览 493人参与
# 实习吐槽大会 #
385856次浏览 2156人参与
# 中美关税战对我们有哪些影响 #
43727次浏览 364人参与
# vivo工作体验 #
28398次浏览 124人参与
# 哪些行业值得去? #
5907次浏览 51人参与
# 中美关系回暖，你会选择出海吗？ #
7430次浏览 110人参与
# 华为保温 #
108370次浏览 408人参与
# 读研or工作，哪个性价比更高？ #
78810次浏览 769人参与
# i人适合做什么工作 #
12095次浏览 98人参与
# 美团开奖 #
225487次浏览 1156人参与
# AI时代，哪些岗位最容易被淘汰 #
3827次浏览 27人参与
# 如果秋招能重来，我会____ #
38679次浏览 311人参与
# 华为池子有多大 #
110631次浏览 750人参与