题目
题目描述: 月月防止别人向华华搭讪,决定以绝后患,让她们没有任何机会。
所以!删掉名字是华华名字子串的小可爱。
第一行输入一个字符串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; } //函数区