题解 | 月月查华华的手机

蒟蒻的我只想得到二分查找每一个字母，但好像没人发使用upper_bound()的版本，遂发出（）

思路：对于华华的昵称字符串A，我们可以预处理每个字母出现的位置，即用一个二维数组a[26][]，其中a[i]按升序存储某个字母在字符串A中出现的所有位置

对于每个推荐好友的昵称字符串B，我们按顺序遍历B的每个字符，并在A中查找该字符出现的位置，当我们匹配B的第i个字符时，需要在A中找到大于前一个字符匹配位置的该字符最早出现的位置，这样就可以保证B是A的一个子序列

具体做法：

1. 用last_idx记录在A中已匹配的最后一个位置，初始化为-1

2. 对于B中的每个字符：

-获取该字符对应的字母索引

-在a[索引]这个有序数组中，用二分查找找到第一个大于last_idx的位置

-如果找不到，说明B不是A的子序列，输出"No"

-如果找到，更新last_idx为该位置

3. 如果B的所有字符都能在A中找到这样的位置，则输出"Yes"

这种方法的时间复杂度为：

-预处理：O(|A|)，其中|A|是字符串A的长度

-每次查询：O(|B| * log|A|)，其中|B|是查询字符串的长度

-总复杂度为O(|A| + N * |B| * log|A|)，能过

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    int len=s.length();
    vector<vector<int>> a(26,vector<int>(0));
    for(int i=0;i<len;i++){
        a[s[i]-'a'].push_back(i);
    }
    int q;
    cin>>q;
    while(q--){
        cin>>s;
        len=s.length();
        int last_idx=-1;
        int f=1;
        for(int i=0;i<len;i++){
            int idx=s[i]-'a';
            auto it=upper_bound(a[idx].begin(),a[idx].end(),last_idx);
            if(it==a[idx].end()){
                f=0;
                break;
            }
            else {
                last_idx=*it;
            }
        }
        if(f) cout<<"Yes\n";
        else cout<<"No\n";
    }
}