NC23053 月月查华华的手机

题目地址：

https://ac.nowcoder.com/acm/problem/23053

基本思路：

1. 我们可以知道原题意就是让我们在给定字符串中q次查询,每次看查询字符串是不是给定字符串子序列;
2. 我们先明确子序列是不需要连续的,即只要保证在原字符串中的位置关系不变就行;
3. 所以我们可以从小到大记录原字符串中每个字母出现的每个位置;
4. 在查询过程中,我们只要每次查询当前需要字符在原字符串中的第一个比查询字符串上一个字符位置后的位置就行了,这里我们可以直接二分查找,然后每次同时记录这个位置为上一个位置记录在next变量里（具体看代码注释）;

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
int q;
string str,temp;
vector<int> memo[26];
signed main() {
  IO;
  cin >> str;
  for (int i = 0; i < str.size(); i++) memo[str[i] - 'a'].push_back(i); //记录每个字符的出现位置;
  cin >> q;
  while (q-- > 0) {
    cin >> temp;
    bool v = true;
    int next = -1;//next初始设为-1;
    for (auto t : temp) {
      //在原字符串的记录数组中二分查找当前字母第一个比上一位置大的位置;
      auto it = upper_bound(memo[t - 'a'].begin(), memo[t - 'a'].end(), next);
      //找不到,就说明不是子序列;
      if (it == memo[t - 'a'].end()) {
        v = false;
        break;
      }
      next = *it;//将这个位置更新为next;
    }
    if (v) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  return 0;
}