序列自动机模板

算法背景

子序列的匹配，当然如果只是少量的模式串，直接使用双指针进行模拟即可，如果遇到大量模式串需要进行匹配，那么可以为主串维护一个DFA，对每一个模式串匹配时间复杂度都是O(n).

算法的大致思想是为每一个主串的字符节点创建一个下一个字符的索引节点，方便状态快速转换。

算法模板

/**
* 初态是 0 
*/
void init() {
    int nxt[MAX_N + 1][27];
    int strLen = s.length();
    for (int i = 0; i <= 25; i++) nxt[strLen][i] = -1;
    for (int i = s.length(); i; i--) {
        for (int j = 0; j < 26; j++) nxt[i - 1][j] = nxt[i][j];
        nxt[i - 1][s[i - 1] - 'a'] = i;
    }
}