竞赛讨论区 > 【每日一题】4月2日题目精讲 枚举优化

【每日一题】4月2日题目精讲 枚举优化

头像
王清楚
编辑于 2020-04-02 15:50:03 APP内打开
赞 1 | 收藏 0 | 回复47 | 浏览1663

题号 NC23053
名称 月月查华华的手机
来源 牛客小白月赛12
戳我进入往期每日一题汇总贴~

暴力的话是但是这样也太暴力了。

这就是个简单的枚举优化,不要认为有多么的复杂高深(学算法最忌讳自己吓唬自己,你怕了就已经输了)。

我们可以观察,比如主串(华华的昵称)是,子串(小姐姐的昵称)是 ,那么当 匹配上了之后,再去枚举主串中的 其实是没有意义的,如果我们能做到在 之后跳到 后面第一个 然后在 之后跳到后面的第一个 (如果有的话),直到子串遍历完或者跳不动了,就能出结果了。(如果主串中有两个一样的字母,我们肯定会选前一个,因为是子序列,如果选前一个不可以,那么选后面的同一个字母肯定就更不可以了,因为选越靠后的字母给后面留下的选择余地就越小。)

那么我们怎么实现在主串跳着枚举这个事情呢?

开一个数组表示主串第 个字母之后的第一个分别在哪一个位置,子串每次与之匹配的时候顺着往后走就行。

next数组的维护只需要从后往前扫描主串,在 扫描到第 位的时候始终维护一个数组 表示当前位置往后最靠前的字母分别在哪,然后把这个数组复制给就可以了。

这样的话每次匹配的复杂度是的(只要顺着Bi遍历完就可以判断是不是子序列了)。总复杂度是
代码可戳我查看~

看完邓老师的题解,记得自己做题提高呀~
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目4月10日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

47条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐