序列自动机

序列:不要求连续

子串:要求连续

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]=等等,同样第一个字符也有这样的26个孩子,这样从根节点到任意一个叶子节点都是原串的一个子序列,这样判断一个字符串t是不是原串的子序列只要将t中的每一个字符在那棵树里跑一下,如果存在这样的路径就表示t是s的一个子序列,

那么怎么建树呢,如果正着建树的话每次都要找到后面最早出现的字符的位置,不太好弄,所以我们倒着建树,用一个 now[26数组表示遍历到第i个字符时后面这26个字符从后往前看最晚出现的位置,也就是第i个字符后面的26个字符最在出现的位置,用它来更新 nxt[i][126],然后再将这个字符在 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 }

 另一方式:

1 void getnext(){//序列自动机
2     for(int i=0;i<26;i++)nex[len][i]=len+1;//不存在赋值为n+1,以便dp时排除掉不可能的情况
3     for(int i=n;i>=1;i--){
4         for(int j=0;j<26;j++)nex[i-1][j]=nex[i][j];
5         nex[i-1][s[i]-'a']=i;
6     }
7 }
原文地址:https://www.cnblogs.com/wsy107316/p/12317349.html