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

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

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

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

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

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

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

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

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

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

活动奖励：

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

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

.牛币兑换中心

牛客博客开通方式

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