在学习和了解序列自动机前,我们要熟悉自动机,“自动机”一般都指“确定有限状态自动机”。自动机是计算机科学中被广泛使用的一个数学模型,其思想在许多字符串算法中都有涉及,因此推荐在学习一些字符串算法(KMP、AC 自动机、SAM)前先完成自动机的学习。学习自动机有助于理解上述算法。
在这就不详细重复说明自动机了,接下来就是序列自动机的内容。
序列自动机是一个可以快速判断字符串t是否是字符串s的子串的一个算法。使用空间复杂度来换取时间复杂度。
构造
对字符串s构造序列自动机,使用nxt数组。nxt[i][j]代表从第i个位置开始,字符j出现的第一个位置。我们倒着遍历更新即可。
int nxt[N][27]; void init(char *s){ int l=strlen(s); for(int i=0;i<26;i++) nxt[l][i]=INF;//初始化 for(int i=l-1;i>=0;i--){ for(int j=0;j<26;j++){ nxt[i][j]=nxt[i+1][j]; } nxt[i][s[i]-'a']=i;//apple nxt[4]['e'-'a']=4 } }
查询
设置初始指针p为-1,每次让p跳到nxt[p+1][j]上面,j为当前查询的字符,如果p为INF,则说明找不到下一个字符,即t不是s的子串。
bool find(char *t){ int pos=-1; int l=strlen(t); for(int i=0;i<l;i++){ pos=nxt[pos+1][t[i]-'a']; if(pos==INF) return 0; } return 1; }
本文固定URL:https://www.dotcpp.com/course/1020