序列自动机

问题引入

如果我们需要一种算法，使其可以将一个字符串的所有子序列表示为一个 DAG（即有向无环图），我们该如何构建？

构建

钦定 $n$ 为字符串的长度，$\Sigma$ 为字符集，$S$ 为字符串，且 $S$ 只会包含小写字母。

我们定义 $nxt_{i,j} (i \leq n,j \in \Sigma)$ 为在 $i$ 位置之后第一个 $j$ 字符出现的位置。

那么我们很容易得出构建方法：

struct SequentialAutomaton {
    int nxt[N][M];
    void init(string s){
        for(int i=s.length()-1;i>=0;i--){//从后往前遍历
            for(int j=1;j<=26;j++)nxt[i][j] = nxt[i+1][j];//将nxt数组从 i+1 转移至 i
            if(s[i] <= 'z' && 'a' <= s[i])nxt[i][s[i] - 'a' + 1] = i + 1;//并且更新状态，从下一个字符转移过来
            //我的nxt数组是从 1 开始的，所以从 s_i（对应了字符串第 i+1 个字符）转移
        }
    }
};

时间复杂度为 $O(n|\Sigma|)$，空间复杂度亦为 $O(n|\Sigma|)$。

显然，$nxt_i$ 只会指向 $j(j>i)$，所以这是一个 DAG。

构建完这个 DAG 后，它能做什么呢？

应用

寻找子序列/子序列匹配

这个十分简单，只需要在 DAG 上贪心的往后跳即可，因为如果 $i$ 无法跳到 $k$，那么 $j(j>i)$ 也一定无法跳到 $k$。

vector<int> Find(string x){
    int pt = 0,i = 0;//pt为当前匹配到的子序列中的位置，i当前字符串s1中跳到的位置
    vector<int> xl;//储存答案的vector
    while(pt!=x.length()){
        if(s1.nxt[i][x[pt] - 'a' + 1])//如果能跳，就贪心的跳 
            i = s1.nxt[i][x[pt] - 'a' + 1],pt++,xl.push_back(i);
        else
            return vector<int>();//如果找不到返回一个空的vector
    }
    return xl;//返回答案
}

时间复杂度为 $O(l)$，其中 $l$ 为 $x$ 的长度。

寻找一个子序列的出现次数

很简单，只要我们除了向后跳之外，我们也可以向下一个相同的找，就可以遍历到他每一个出现的情况。

int dfs(string x,int i = 0,int pt = 0){
    int anss = 0;
    //有两种可能
    //第1种，向后跳，此时将pt++
    if(pt != x.length() && s1.nxt[i][x[pt] - 'a' + 1]){
        anss += dfs(x,s1.nxt[i][x[pt] - 'a' + 1],pt+1);
    }
    //第2种，跳到下一个跟自己一样的
    if(pt>0 && s1.nxt[i][x[pt - 1] - 'a' + 1]){
        anss += dfs(x,s1.nxt[i][x[pt - 1] - 'a' + 1],pt);
    }
    if(pt == x.length()){
        //找完了
        return anss+1;
    }
    //此处注意到自己是由 pt-1 跳过来的
    return anss;
}

然后呢，我们发现时间复杂度是极高的，很容易超出时间限制，所以我们需要进行优化。

这个时候，我们就需要使用——记忆化搜索！

借助记忆化搜索，我们只用多开一个 $O(nl)$ 的数组，就可以将时间复杂度压缩到 $O(nl)$ 以下。

int dfs(string x,int i = 0,int pt = 0){
    if(f[i][pt]){
        return f[i][pt];
    }
    int anss = 0;
    //有两种可能
    //第1种，向后跳，此时将pt++
    if(pt != x.length() && s1.nxt[i][x[pt] - 'a' + 1]){
        anss += dfs(x,s1.nxt[i][x[pt] - 'a' + 1],pt+1);
    }
    //第2种，跳到下一个跟自己一样的
    if(pt>0 && s1.nxt[i][x[pt - 1] - 'a' + 1]){
        anss += dfs(x,s1.nxt[i][x[pt - 1] - 'a' + 1],pt);
    }
    if(pt == x.length()){
        //找完了
        return anss+1;
    }
    //此处注意到自己是由 pt-1 跳过来的
    f[i][pt] = anss;//记忆答案
    return anss;
}

统计本质不同子序列数量

我们可以考虑直接深搜，统计所有可能的子序列，并且使用记忆化搜索即可。

int f[N];
int dfs(int x){
    if(f[x])//还是记忆化搜索
        return f[x];
    for(int i=1;i<=26;i++)
        if(s1.nxt[x][i]) 
            f[x] += dfs(s1.nxt[x][i]);//进行转移即可
    if(x)//这里的判断是为了不统计空序列
        f[x]++;
    return f[x];
}

时间复杂度是 $O(n|\Sigma|)$，非常简单。

统计多个字符串之间公共子串数量

例题：P1819 和 P3856

终于进入正题了，这两道题除了取模和有一题要多输入一个长度之外没有区别，就一起讲了。

我们考虑直接对统计本质不同子序列数量进行改造，如果 $s1.nxt_{x,i} \land s2.nxt_{y,i} \land s3.nxt_{z,i}$，则将 $x,y,z$ 分别跳向 $s1.nxt_{x,i},s2.nxt_{y,i},s3.nxt_{z,i}$ 即可。

当然，我们仍然要使用记忆化搜索优化，空间复杂度为 $O(n^3)$，时间复杂度为 $O(n^3|\Sigma|)$。

int f[N][N][N];
int dfs(int x,int y,int z){
    if(f[x][y][z])//记~忆~化~搜~索~
        return f[x][y][z];
    for(int i=1;i<=26;i++)
        if(s1.nxt[x][i] && s2.nxt[y][i] && s3.nxt[z][i]) 
            f[x][y][z] += dfs(s1.nxt[x][i] , s2.nxt[y][i] , s3.nxt[z][i]);
    if(x && y && z)//为了不统计空序列（当然你也可以在输出答案时减一）
        f[x][y][z]++;
    return f[x][y][z];
}

好了，序列自动机以及这道题目就讲到这里 byebye~