【每日一题】4月2日题目精讲 枚举优化
题号 NC23053
名称 月月查华华的手机
来源 牛客小白月赛12
戳我进入往期每日一题汇总贴~
暴力的话是但是这样也太暴力了。
这就是个简单的枚举优化，不要认为有多么的复杂高深（学算法最忌讳自己吓唬自己，你怕了就已经输了）。
我们可以观察，比如主串（华华的昵称）是，子串（小姐姐的昵称）是
，那么当
匹配上了之后，再去枚举主串中的
其实是没有意义的，如果我们能做到在
之后跳到
后面第一个
然后在
之后跳到后面的第一个
（如果有的话），直到子串遍历完或者跳不动了，就能出结果了。（如果主串中有两个一样的字母，我们肯定会选前一个，因为是子序列，如果选前一个不可以，那么选后面的同一个字母肯定就更不可以了，因为选越靠后的字母给后面留下的选择余地就越小。）
那么我们怎么实现在主串跳着枚举这个事情呢？
开一个数组表示主串第
个字母之后的第一个
分别在哪一个位置，子串每次与之匹配的时候顺着往后走就行。
next数组的维护只需要从后往前扫描主串，在 扫描到第 位的时候始终维护一个数组
表示当前位置往后最靠前的字母
分别在哪，然后把这个数组复制给
就可以了。
这样的话每次匹配的复杂度是的（只要顺着Bi遍历完就可以判断是不是子序列了）。总复杂度是
代码可戳我查看~
看完邓老师的题解，记得自己做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！
活动奖励：
在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）
本道题目4月10日中午12：00之前写的题解有获得牛币资格~
牛客博客开通方式
- 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
- 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴
