序列自动机

序列：不要求连续

子串：要求连续

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 }

序列自动机

原文：https://www.cnblogs.com/wsy107316/p/12317349.html