关注
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
相关推荐
_hengheng:22届的,个人的实践是社招最好也别超过2页,一页半左右比较好,有时候去线下终面简历还会被打印出来拿在手里,写太多不太合适,再就是面试顶多一个小时多点,也聊不了那么多内容,反而如何让一页半的简历看起来全是优点才是最重要的,哪一部分都能拿出来和面试官一起交流很久 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 秋招开始捡漏了吗 #
5336次浏览 27人参与
# 今年秋招还有金九银十吗 #
15453次浏览 115人参与
# “vivo”个offer #
44558次浏览 298人参与
# 秋招,不懂就问 #
327396次浏览 1963人参与
# 辞职后的日常 #
15155次浏览 83人参与
# 上班后,才发现大学__白学了 #
180次浏览 8人参与
# 满帮集团求职进展汇总 #
7508次浏览 70人参与
# 打工人的精神状态 #
100096次浏览 1304人参与
# 一人一个landing小技巧 #
126894次浏览 1462人参与
# 我和mentor的爱恨情仇 #
78811次浏览 434人参与
# 上班到公司第一件事做什么? #
98193次浏览 680人参与
# 秋招结束之后的日子 #
99465次浏览 1011人参与
# 海信求职进展汇总 #
84555次浏览 408人参与
# 学历or实习经历,哪个更重要 #
191968次浏览 1026人参与
# 实习期间如何提升留用概率? #
189248次浏览 1605人参与
# 被同事甩锅了怎么办 #
24844次浏览 100人参与
# 你见过哪些工贼行为 #
31297次浏览 151人参与
# 和mentor 1on1 都聊什么? #
3392次浏览 21人参与
# 校招生月薪1W算什么水平 #
47729次浏览 249人参与
# 你想留在一线还是回老家? #
63460次浏览 537人参与
# 入职第一天,你准备什么时候下班 #
88296次浏览 478人参与
查看9道真题和解析