序列自动机

例题：Subsequence 题目链接：点击这里 题目大意：给你一个模式串 $s$ ，再给出 $n$ 个字符串，问这些字符串是否为 $s$ 的子串 构造时把 $len$ 设置为 $inf$ 然后从后往前递推 查询时从前往后查询即可 细节见代码：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #define ll long long #define inf 0x3f3f3f3f using namespace std; int read() { int res = 0,flag = 1; char ch = getchar(); while(ch<'0' || ch>'9') { if(ch == '-') flag = -1; ch = getchar(); } while(ch>='0' && ch<='9') { res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0'; ch = getchar(); } return res*flag; } const int maxn = 1e5+5; const int mod = 1e9+7; const double pi = acos(-1); const double eps = 1e-8; char s[maxn],t[maxn]; int nxt[maxn][27];//nxt[i][j]表示第i个位置开始，字符j出现的第一个位置 void init(char *s) { int len = strlen(s); for(int i = 0;i < 26;i++) nxt[len][i] = inf; for(int i = len-1;i >= 0;i--) { for(int j = 0;j < 26;j++) nxt[i][j] = nxt[i+1][j]; nxt[i][s[i]-'a'] = i; } } bool query(char *s) { int pos = -1,len = strlen(s); for(int i = 0;i < len;i++) { pos = nxt[pos+1][s[i]-'a']; if(pos == inf) return false; } return true; } int main() { scanf("%s",s); init(s); int tt = read(); while(tt--) { scanf("%s",t); if(query(t)) puts("YES"); else puts("NO"); } return 0; }