序列自动机

序列自动机是一个可以快速判断字符串t是否是字符串s的子序列的一个算法。

序列自动机基础

1. 初始化：对s构造序列自动机，使用 代表从第i个位置开始，字符j出现的第一个位置。我们倒着遍历更新即可。

const int maxn = 1e6+1;
const int inf = 0x3f3f3f3f;

char s[maxn], t[maxn];  // 原串与子串
int Nxt[maxn][26]; // 序列自动机的存储

void init(int n) { // 序列自动机初始化
    for(int i = 0; i < 26; ++ i) Nxt[n+1][i] = inf;
    for(int i = n; i >= 1; -- i) {
        for(int j = 0; j < 26; ++ j) {
            Nxt[i][j] = Nxt[i+1][j];
        }
        Nxt[i][s[i]-'a'] = i;
    }
}

序列自动机拓展

2. 判断 t 是否为 s 的子序列：设置初始指针pos为0，每次让pos跳到 上面，j为当前查询的字符，如果pos为INF,则说明找不到下一个字符，即t不是s的子序列。

bool check(int m) { // 判断长度为m的子串是否是原串的子序列
    int pos = 0;
    for(int i = 1; i <= m; ++ i) {
        pos = Nxt[pos+1][t[i]-'a'];
        if (pos == inf) return false;
    }
    return true;
}

3. 计算 s 与 t 的最长公共子序列（时间复杂度 ）：设 dp[i][j] 表示与 t[1..i] 的公共序列长度达到 j 的 A[1..n] 的最短前缀的长度，利用 Nxt 数组进行转移。 注：m = |t|

int dp[maxn][maxn]; // 以t的第i位结尾，且与s的最长公共子序列长度为j的最小下标

int lcs(int m) { // 序列自动机 + dp 求最长公共子序列
    for(int i = 0; i <= m; ++ i) {
        for(int j = 0; j <= i; ++ j) {
            dp[i][j] = inf;
        }
    }
    dp[0][0] = 0;
    for(int i = 0; i < m; ++ i) {
        for(int j = 0; j <= i; ++ j) {
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
            if (dp[i][j] != inf) dp[i+1][j+1] = Nxt[dp[i][j]+1][t[i+1]-'a'];
        }
    }
    int res = 0;
    for(int i = 1; i <= m; ++ i) {
        if (dp[m][i] != inf) res = i;
    }
    return res;
}

专题

http://acm.hdu.edu.cn/showproblem.php?pid=1159 【拓展.3】
http://acm.hdu.edu.cn/showproblem.php?pid=6774 【拓展.3】