题目

题目描述:
月月防止别人向华华搭讪,决定以绝后患,让她们没有任何机会。
所以!删掉名字是华华名字子串的小可爱。

输入描述:
第一行输入一个字符串A表示华华的昵称。
第二行输入一个正整数N表示华华的推荐好友的个数。
接下来N行,每行输入一个字符串 B表示某个推荐好友的昵称。

输出描述:
输出N行,对于第i个推荐好友,如果华华可能向她搭讪,输出Yes,否则输出No。
注意大写,同时也要注意输出效率对算法效率的影响。


解析

这道题第一眼看到是枚举,第二眼看是kmp,kmp是算连续子串的,放弃。没想到真的是枚举。

  • 这道题的主要内容就是:枚举优化。也就是用一些方法让枚举变得简单一点呗。

那用的是咋办呢?
  1. 我们在搜索的过程中总会碰到很多没必要的字母,但是遍历的时候为了查找,我们还是要一个一个判断过去。
  2. 但是我们能不能用一个方法,不去判断这些东西。直接跳转到我们下一个要的字母的位置呢?
  3. 当然可以,我们在学kmp的时候就学过的kmp数组,不就是用来找匹配串在某一点前面最近的字母的吗。这里我们可以用类似的方法。

那用啥方法呢?
  1. 我们首先用一个last数组保存下,当前情况每个字母最靠前的位置(last里面保存0~25,表示26个字母,last[字母] = 位置)。
  2. 我们刚刚说到了当前情况,因为我们要判断现在nxt数组的情况:我们给nxt数组加了一维:nxt[i][j]表示 i 为起点向后,j 字母的位置
  3. 所以nxt数组简单来说就是:next[起点][字母] = 起点后第一个位置
  4. 然后我们查找的时候一个一个字母的往后查找就好了,没找到就没有呗。

咋操作呢?
  1. 我们要确定这个二维数组,当然要用一个双层循环:我们要求的是,每种情况下,每个字母的位置
  2. 所以我们的内层循环当然要遍历26个字母,而且我们开始就说了建立了一个last数组,就把last数组赋值给next就行了
  3. 然后外层循环是遍历情况,情况也就是以每个位置为起点,所以是遍历母串数组。
  4. 遍历母串的时候,我们就可以顺便把每一个字母散列记录到last数组里面啦。

好了好了,打代码吧:
  1. 先输入该输入呗。
  2. 然后按照我们上面的算法讲解初始化。
  3. 然后我们就可以循环查找了,不难不难。
  4. 看代码吧~


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;
}
//函数区