序列：不要求连续
子串：要求连续
AC自动机，kmp都是匹配子串的；序列自动机是匹配序列的
参考博客：https://www.cnblogs.com/31415926535x/p/10504504.html
序列自动机实质还是用空间换时间，它有一个数组 nxt[i][j](nxt[maxn][26]），表示原串s的第i位后面那26个字符j出现的最早的 位置，
相当于建了一棵树，根节点是一个空节点，它有26个孩子，表示每一个字母最早出现的位置，那么原串的第一个字符 s[0] 就使得 nxt[0][s[0]−′a′]=1，第二个字符就是 nxt[0][s[1]−′a′]=2 等等，同样第一个字符也有这样的26个孩子，这样从根节点到任意一个叶子节点都是原串的一个子序列，这样判断一个字符串t是不是原串的子序列只要将t中的每一个字符在那棵树里跑一下，如果存在这样的路径就表示t是s的一个子序列，
那么怎么建树呢，如果正着建树的话每次都要找到后面最早出现的字符的位置，不太好弄，所以我们倒着建树，用一个 now[26] 数组表示遍历到第i个字符时后面这26个字符从后往前看最晚出现的位置，也就是第i个字符后面的26个字符最在出现的位置，用它来更新 nxt[i][1→26]，然后再将这个字符在 now 数组中的位置更新为当前的位置，now[s[i]−′a′]=i，
实现：
1 #include <bits/stds++.h>
2 using namespace std;
3 #define rep(i,first,last) for(int i=first;i<=last;i++)
4 #define dep(i,first,last) for(int i=first;i>=last;i--)
5 const int maxn = 10010;
6 int nxt[maxn][30];
7 int now[30];
8 char s[maxn];
9
10 void init(){
11 memset(now,-1,sizeof(now));
12 int len=strlen(s);
13 dep(i,len-1,0){
14 rep(j,0,25){
15 nxt[i][j]=now[j];
16 }
17 now[s[i]-'a']=i;
18 }
19 }
