在學(xué)習(xí)和了解序列自動機前，我們要熟悉自動機，“自動機”一般都指“確定有限狀態(tài)自動機”。自動機是計算機科學(xué)中被廣泛使用的一個數(shù)學(xué)模型，其思想在許多字符串算法中都有涉及，因此推薦在學(xué)習(xí)一些字符串算法（KMP、AC 自動機、SAM）前先完成自動機的學(xué)習(xí)。學(xué)習(xí)自動機有助于理解上述算法。

在這就不詳細(xì)重復(fù)說明自動機了，接下來就是序列自動機的內(nèi)容。

序列自動機是一個可以快速判斷字符串t是否是字符串s的子串的一個算法。使用空間復(fù)雜度來換取時間復(fù)雜度。

構(gòu)造

對字符串s構(gòu)造序列自動機，使用nxt數(shù)組。nxt[i][j]代表從第i個位置開始，字符j出現(xiàn)的第一個位置。我們倒著遍歷更新即可。

    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
        }
    }

查詢

設(shè)置初始指針p為-1，每次讓p跳到nxt[p+1][j]上面，j為當(dāng)前查詢的字符，如果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;
}