【每日一题】月月查华华的手机
月月查华华的手机
https://ac.nowcoder.com/acm/problem/23053
题目
题目描述： 月月防止别人向华华搭讪，决定以绝后患，让她们没有任何机会。
所以！删掉名字是华华名字子串的小可爱。
第一行输入一个字符串A表示华华的昵称。
第二行输入一个正整数N表示华华的推荐好友的个数。
接下来N行，每行输入一个字符串 Bi 表示某个推荐好友的昵称。
输出N行，对于第i个推荐好友，如果华华可能向她搭讪，输出Yes，否则输出No。
注意大写，同时也要注意输出效率对算法效率的影响。
解析
这道题第一眼看到是枚举，第二眼看是kmp，kmp是算连续子串的，放弃。没想到真的是枚举。
- 这道题的主要内容就是：枚举优化。也就是用一些方法让枚举变得简单一点呗。
那用的是咋办呢？
- 我们在搜索的过程中总会碰到很多没必要的字母，但是遍历的时候为了查找，我们还是要一个一个判断过去。
- 但是我们能不能用一个方法，不去判断这些东西。直接跳转到我们下一个要的字母的位置呢？
- 当然可以，我们在学kmp的时候就学过的kmp数组，不就是用来找匹配串在某一点前面最近的字母的吗。这里我们可以用类似的方法。
那用啥方法呢？
- 我们首先用一个last数组保存下，当前情况每个字母最靠前的位置（last里面保存0~25，表示26个字母，last[字母] = 位置）。
- 我们刚刚说到了当前情况，因为我们要判断现在nxt数组的情况：我们给nxt数组加了一维：nxt[i][j]表示 i 为起点向后，j 字母的位置
- 所以nxt数组简单来说就是：next[起点][字母] = 起点后第一个位置。
- 然后我们查找的时候一个一个字母的往后查找就好了，没找到就没有呗。
又咋操作呢？
- 我们要确定这个二维数组，当然要用一个双层循环：我们要求的是，每种情况下，每个字母的位置。
- 所以我们的内层循环当然要遍历26个字母，而且我们开始就说了建立了一个last数组，就把last数组赋值给next就行了。
- 然后外层循环是遍历情况，情况也就是以每个位置为起点，所以是遍历母串数组。
- 遍历母串的时候，我们就可以顺便把每一个字母散列记录到last数组里面啦。
好了好了，打代码吧：
- 先输入该输入呗。
- 然后按照我们上面的算法讲解初始化。
- 然后我们就可以循环查找了，不难不难。
- 看代码吧~
AC代码
#include <iostream>
#include <cstring>
using namespace std;
#define js ios::sync_with_stdio(false);
//代码预处理区
const int MAX = 1e6 + 7;
char A[MAX];//母串
int last[30], nxt[MAX][30];//每个字母的最后位置，next[起点][字母] = 起点后第一个位置
//全局变量区
void init();
int judge(char s[]);
//函数预定义区
int main() {
js;
cin >> A;
init();
int N; cin >> N;
while (N--) {
char s[MAX]; cin >> s;
if (judge(s)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
void init() {
memset(last, -1, sizeof last);
for (int i = strlen(A) - 1; i >= 0; i--) {
for (int j = 0; j < 26; j++)
nxt[i][j] = last[j];
last[A[i] - 'a'] = i;
}
//从最后一个字符往前，初始化nxt数组的值
}
int judge(char s[]) {
int len = strlen(s);
int pos = last[s[0] - 'a'];//第一个字母的位置
if (-1 == pos) return 0;
for (int i = 1; i < len; i++) {
pos = nxt[pos][s[i] - 'a'];
if (-1 == pos) return 0;
}
//循环查找每一个字母的位置，没有则返回false
return 1;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
查看5道真题和解析
