关注
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
相关推荐
rush$0522:转正名单没进,大概率本来就没打算留你 点赞 评论 收藏
分享
李橙子:你这如果想找java方向的,那你的项目就不要写python啊,不然会以为你是主要找python的 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 今年春招是金一银二嘛? #
28336次浏览 261人参与
# 帆软软件工作体验 #
10372次浏览 47人参与
# 没关系,至少我的__很曼妙 #
12079次浏览 193人参与
# 软开人,秋招你打算投哪些公司呢 #
176606次浏览 1321人参与
# 牛客吐槽大会 #
10434次浏览 189人参与
# 机械制造2024笔面经 #
1515136次浏览 12994人参与
# AI求职实录 #
17185次浏览 397人参与
# 秋招被确诊为…… #
286604次浏览 1595人参与
# 快手年终开大包 #
3926次浏览 52人参与
# 抛开难度不谈,你最想去哪家公司? #
15649次浏览 222人参与
# 为什么有人零实习也能进大厂? #
14629次浏览 252人参与
# 你的第一家实习公司是什么档次? #
12905次浏览 138人参与
# 赚钱的意义在这一刻具象化 #
11506次浏览 219人参与
# 考研人,我有话说 #
164036次浏览 1243人参与
# 1月小结:你过的开心吗? #
5041次浏览 85人参与
# 总结:哪家公司面试体验感最好 #
79665次浏览 445人参与
# Prompt分享 #
17941次浏览 415人参与
# AI时代的工作 VS 传统时代的工作,有哪些不同? #
16517次浏览 375人参与
# 工作中哪个瞬间让你想离职 #
119715次浏览 802人参与
# 实习最想跑路的瞬间 #
113214次浏览 695人参与
查看1道真题和解析
深信服公司福利 891人发布