[每日一题]4.1 月月查华华的手机

• 涉及知识点：字符串匹配

• 题意：给出母串 s，给出 m 次询问，每次询问给出的子串 si 是否是 s 的子序列

• 思路：如果直接考虑双重for循环比较会超时，看着是道字典树的题，但是没写过字典树，就写了个递推思路的代码，设 nex[ i ][ j ] 表示第 i 个位置的字母后第一个 j + 'a' 字母的位置，提前预处理母串s，查询子串 si 就可以简化到O( n )

• 代码：

  #include <bits/stdc++.h>
  using namespace std;
  #define ll long long
  const int maxn = 1e6 + 5;
  char s[maxn];
  int nex[maxn][26];
  int main()
  {
    scanf("%s",s+1);
    int l = strlen(s+1);
    for(int i=l-1;i>=0;i--)
    {
        for(int j=0;j<26;j++)
        {
            nex[i][j] = nex[i+1][j];
        }
        nex[i][s[i+1]-'a'] = i+1;
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s+1);
        l = strlen(s+1);
        int k = 0,flag = 0;
        for(int i=1;i<=l;i++)
        {
            if(nex[k][s[i]-'a']){
                k = nex[k][s[i]-'a'];
            }
            else{
                flag = 1;
                break ;
            }
        }
        if(flag)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
  }
  

```