牛客每日一题4.2 月月查华华的手机 二分查找

https://blog.csdn.net/qq_43804974/article/details/105241744

问题就是询问某一个串是不是初始串的子序列。
那么序列都是小写字母，就对存入每一个字母在初始串的位置。然后对目标串的字母一个个查询，如果存在一个最接近并且比上一个字母远的位置，则这个当前字母是存在序列中的，不断的遍历完整个目标串就可以了。开个vector，upper_bound真香

char node[max_],temp[max_];
vector<int> ind[30];
signed main() {
//    scanf_s("%s", node + 1);
    cin >> node + 1;
    int len = strlen(node + 1);
    for (int i = 1; i <= len; i++) {
        ind[node[i] - 'a'].push_back(i);
    }
    int T; cin >> T;
    while (T--){
        cin >> temp + 1;
        int len = strlen(temp + 1);
        int flag = 1,now = 0;
        for (int i = 1; i <= len; i++) {
            int wei = upper_bound(ind[temp[i] - 'a'].begin(), ind[temp[i] - 'a'].end(), now) - ind[temp[i] - 'a'].begin();
            if (wei >= ind[temp[i] - 'a'].size()) {
                flag = 0; break;
            }
            now = ind[temp[i] - 'a'][wei];
        }
        if (flag) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
    }
    return 0;
}