序列自动机概述

67797 阅读 0 评论 0 点赞

在学习和了解序列自动机前，我们要熟悉自动机，“自动机”一般都指“确定有限状态自动机”。自动机是计算机科学中被广泛使用的一个数学模型，其思想在许多字符串算法中都有涉及，因此推荐在学习一些字符串算法（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;
}