一开始以为是kmp，结果发现是子序列，不要求连续。

题意：
给出一个字符串s，接着给m个询问，每次询问一个字符串p,问p是否是s的子序列。
len(s)<=10^6,m<=10^6，∑p<=10^6.

思路：
一开始想的是，预处理出s中的每个字母依次出现的位置，在询问的时候维护当前已经到达的位置pos，然后找出第一个大于pos的字母p[i]的位置。结果超时了。
后来考虑到可能对每个字母查找位置的时候有点浪费时间，于是改成了二分查找，结果还是超。。
无奈，看了一下题解。
用nxt[i]['a'-'z']表示第i个位置后面第一次出现某个字母的位置。
这里我们可以维护一个la[j]数组表示字母j的最左侧位置。因此我们可以从后往前扫描字符串s，然后预处理出nxt数组。
在每次询问的时候，我们直接维护当前位置now，然后直接利用nxt[now][p[i]]跳就可以了。
复杂度主要是在预处理中，为O（26*10^6）

代码：

#include<bits/stdc++.h>
using namespace std;
string s;
int nxt[1000050][26],la[26];
int main()
{
    cin>>s;
    for(int i=s.size()-1;i>=0;i--){
        int tmp=s[i]-'a';
        for(int j=0;j<26;j++)nxt[i+1][j]=la[j];
        la[tmp]=i+1;
    }
    for(int j=0;j<26;j++)nxt[0][j]=la[j];
    int m;
    cin>>m;
    string p;
    while(m--){
        cin>>p;
        int now=0;
        bool flag=true;
        for(int i=0;i<p.size();i++){
            if(nxt[now][p[i]-'a'])now=nxt[now][p[i]-'a'];
            else {
                flag=false;
                break;
            }
        }
        if(flag)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}