题解 | 月月查华华的手机

#include <iostream>
#include<cstring>
using namespace std;
const int N=1e6+10;
int a[N][26];//用来储存字符串第k个位置后的字母最近出现的位置
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s;
    cin>>s;
  //这里把i=0看作虚拟起点 同时也避免了过程中出现0 将0作为不存在的标志  这样一来就得把字符串范围当作1-n
    for(int i=s.size()-1;i>=0;i--){//因为是找后面的最近出现的位置 故采用倒序可以继承
        for(int j=0;j<26;j++){
            a[i][j]=a[i+1][j];
            }
        a[i][s[i]-'a']=i+1;//更新 我们下标从1开始但字符串是从0开始
    }
    int n;
    cin>>n;
    while(n--){
        string c;
        cin>>c;
        int now=0;
        bool st=true;;
        for(int i=0;i<c.size();i++){
            if(a[now][c[i]-'a']==0){
                st=false;
                break;//没有直接结束
            }
            else{
                now=a[now][c[i]-'a'];//有的更新下一个位置
            }
        }
        if(st)cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

用双指针会爆掉

采取这种预处理下一位置的方法,进行查找复杂度为o(1)不会超时

由于是处理下一位置,为了继承我们采取倒序的方法

还要考虑开头匹配,引入虚拟起点