子串查询（子序列查询）

 好累，明明今天什么都没写，就是心好累，不想玩了QwQ

A-子串查询_牛客竞赛字符串专题班Hash（Hash的三种姿势及应用）（重现赛）@lamentropetion (nowcoder.com)

题意：

思路：

 对于s，预处理出每个字符在i位置后缀第一个出现j字母的位置

然后对于一个询问串，去跳着找下一个在原串中匹配的字符

如果没找到就是NO，全部匹配了就是YES

Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn=5e4+10;
const int mxe=5e4+10;
const int Inf=0x3f3f3f3f;int n,q,len;
int dp[mxn][30];
string s,t;
void solve(){cin>>n>>q>>s;s=" "+s;memset(dp,0x3f,sizeof(dp));for(int i=n;i>=1;i--){dp[i][s[i]-'a'+1]=i;for(int j=1;j<=26;j++) dp[i][j]=min(dp[i][j],dp[i+1][j]);}while(q--){t.clear();cin>>t;len=t.size();t=" "+t;int p=1;for(int i=1;i<=len;i++){p=dp[p][t[i]-'a'+1];if(p>=Inf) break;p++;}if(p>=Inf) cout<<"NO"<<'\\n';else cout<<"YES"<<'\\n';}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}