贴一题：
https://ac.nowcoder.com/acm/contest/543/B
题意： 输入一个人字符串a，再输入一个字符串b, 问b是否是a的子序列，是则输出Yes，否则输出No。
思路：
暴力肯定是会超时的，既然时间会超，那么只能用空间换时间，采用一个比较冷门的算法 -----------------------> 子序列自动机。
子序列自动机适合于字符串中的字符种类数偏少，且已知。
思路很简单，假设 主序列 为 “abcade”
建立一个二维数组 dis【MAX】【30】； // 此处的30是字符种数， 这里是字符取 ‘a‘ ~ ‘z‘ 种数是 26。
直接输出dis数组，那你就懂了。
对于 “abcade” 对于dis数组，假设dis[i][j] 为-1，说明 ASCII值为 ‘a‘+j 的字符，在位置 >= i 之后不存在。
如果为非-1，假设为整数 b , 同理，该字符，在位置 >=i 之后最近的为位置 b
附上代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<queue> #include<stack> #include<algorithm> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define Mem0(x) memset(x,0,sizeof(x)) #define Mem1(x) memset(x,-1,sizeof(x)) #define MemX(x) memset(x,0x3f,sizeof(x)) using namespace std; typedef long long ll; const int inf=0x3f3f3f; const int MAX=1e6+10; char str1[MAX],str2[MAX]; int dfs[MAX][30],res[30]; int main() { int n; cin>>str1+1>>n; int len=strlen(str1+1); for (int i=0;i<26;i++) res[i]=-1; for (int i=len;i>=0;i--){ for (int j=0;j<26;j++){ dfs[i][j]=res[j]; } res[str1[i]-‘a‘]=i; } while (n--){ cin>>str2+1; int len1=strlen(str2+1); bool flag=true; int tmp=0; for (int i=1;i<=len1;i++){ if (dfs[tmp][str2[i]-‘a‘]==-1){ flag=false; break; } tmp=dfs[tmp][str2[i]-‘a‘]; } if (flag) printf("Yes\n"); else printf("No\n"); } return 0; }
原文：https://www.cnblogs.com/q1204675546/p/10617622.html