字符串

思路：
首先可以想到一个暴力的做法就是拿子串与模式串一一匹配，时间复杂度O(n^2)(讲道理这个应该是过不了的，但是我居然过了。。)
然后就是考虑一下怎么优化，（看的题解，感觉挺奇妙的）就题目不是说字符串只可能是小写字母[a,z]，那么我们可以构造一个next[i][j]:表示模式串第i个字符到字符j的下标，有了一个东西如果我们进行匹配的话就可以省去多余的没用的匹配，比如abcdef,子串ac,我们匹配完a，直接next[a][c] = 3,这样就直接去和第三个字符匹配，那么next数组怎么构造呢，还需要一个last[i]:表示字符i距离前面字符的最近位置，这样从后往前面扫就可以构造next数组了。然后这题就出来了。
O(n^2)代码：

#include<bits/stdc++.h>
using namespace std;

void solved(){
    string mo;cin>>mo;
    int n;cin>>n;
    vector<string>ve;
    for(int i = 1; i <= n; i++){
        string a;cin>>a;
        ve.push_back(a);
    }
    //noiauwfaurainairtqltqlmomomo
    //1
    //ooooo
    for(int i = 0; i < ve.size(); i++){
        string s = ve[i];
        int cnt = 0;
        int r = 0;
        for(int i = 0; i < s.size(); i++){
            while(s[i] != mo[r] && r < mo.size())r++;
            if(s[i] == mo[r]){cnt ++; r++;}
            if(r >= mo.size())break;
        }
        if(cnt == s.size())cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}
int main(){
    solved();
    return 0;
}

O(26n)代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
char mo[maxn];
char pi[maxn];
int nxt[maxn][30];
int last[100];
//next[i][j]:表示模式串中第i个字符到字符z的位置 j=[a,z] 
void solved(){
    scanf("%s",mo + 1);
    int n;cin>>n;
    int len = strlen(mo + 1);
    memset(last,-1,sizeof(last));
    for(int i = len; i >= 0; i--){
        for(int j = 1; j <= 26; j++){
            nxt[i][j] = last[j];//第i个字符到字符j的位置 
        }
        last[mo[i] - 'a' + 1] = i;
    }

    while(n--){
        scanf("%s",pi + 1);
        int len = strlen(pi + 1);
        int k = nxt[0][pi[1] - 'a' + 1];
        //cout<<k<<endl;
        if(k == -1){
            cout<<"No"<<endl;continue;
        }
        for(int i = 2; i <= len; i++){
            k = nxt[k][pi[i] - 'a' + 1];
            if(k == -1)break;
        //    cout<<k<<endl;
        }
        if(k != -1)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}
int main(){
    solved();
    return 0;
}