[可能有用科技]子序列自动机

前言

我可能是有点大病才来学这种东西.

本来想去写计算几何和LCT,但是我太菜了学不会于是去写了一个广义 SAM 板子 甚至还 WA 了四次.

遂来学怪东西.

update from 学到一半:

我超fxj开卷多项式牛顿迭代了,好强!

子序列自动机

神 \mathrm{{\color{balck}w}{\color{red}ind\_whisper}} 说 : 所谓后缀自动机，就是通过后缀建立的自动机.

好像跑题了.

不要紧.

神 \mathrm{{\color{balck}w}{\color{red}ind\_whisper}} 说 : 所谓子序列自动机，就是通过子序列建立的自动机.

顾名思义,序列自动机可以且仅可以接受一个信号序列的子序列的自动机.

前缀后缀和子串都是子序列,无敌了!

这个自动机最大的问题是太 "博爱" 了,也就是能接受任原字符串任意的子序列且所有状态都是接受状态,导致无法解决有些只能考虑子串的情况.

首先我们再利用一下所学过最简单普适的自动机结构 : Tire.

把每一个子序列插入 trie 里.

然后这个想法已经超越了 naive , 简直是愚蠢.

然后再想一个想法,反正会出现大量的重复情况,不如放弃具体表述,每个状态只表示转移到那个位置.

然后就是一个 n + 1 个状态的自动机.

一个空状态,可以转移到以后每个状态.

然后 n 个状态,只能向更后面的任意状态转移.

且每个状态都是可接受的.

但是这样显然不行,因为无用的转移太多了.

考虑这样一个情况 : 字符串 aabbaa

初始状态 st_0 只有两种可行的转移种类 a,b 但是照上一种方式构造,却有六个可行转移选项,这显然是不优的.

那么贪心地想,反正可以向后面任意的转移,对于一类转移只需要求一个最考前的就完事了.

目前的建立时间是 \mathcal{O} (n^2),相比其他的自动机都是线性,显然这太拉了,想办法优化一下.

那么直接记录一下每种字符上一个出现的位置然后倒着建即可,复杂度降为 \mathcal{O} (n|\Sigma|).

但是可以发现这时候字符集很大地影响了复杂度,如果字符集太大(例如洛谷上子序列自动机的模板)甚至建立的时候会直接 TLE.

考虑直接对于每个字符存储一下其出现的位置,然后转移就靠二分查找即可.

Code 1 : 查询线性

constexpr int S = 26;// |Sigma|
struct SubsequenceAutomaton {
    int len;
    int ch[N][S];
    inline void build(char *v,int n) {
        static int nxt[S];len = n + 1;
        rep(i,0,S - 1) nxt[i] = n + 1;
        repb(i,n,0) {
            memcpy(ch[i],nxt,sizeof(nxt));
            nxt[v[i] - 'a'] = i;
        }
    }

    inline bool query(char *s) {
        bool flag = 1;int p = 0;
        for(int i = 0;s[i];++i) {
            if(ch[p][s[i] - 'a'] == len + 1) {
                flag = 0;
                break;
            }
            p = ch[p][s[i] - 'a'];
        }
        return flag;
    }
}SQAM;

Code 2 : 查询带 \log

constexpr int S = 100005;
struct SubSequenceAutomaton {
    std::vector<int> st[S];

    inline void build(int *v,int n) {
        rep(i,1,n) st[v[i]].push_back(i);
    }

    inline bool query(int *t,int n) {
        bool flag = 1;int p = 0;
        rep(i,1,n) {
            std::vector<int>::iterator pos =
            std::upper_bound(st[t[i]].begin(),st[t[i]].end(),p);
            if(pos == st[t[i]].end()) {
                flag = 0;
                break;
            }
            p = *pos;
        }
        return flag;
    }
}SQAM;

例题

P5826 【模板】子序列自动机

字符集比较大,需要使用第二种.

P4112 [HEOI2015]最短不公共子串

使用第一种.

大杂烩题,需要 SAM.

首先看到题就知道这个玩意四倍常数,估计是 \mathcal{O} (n^2) 的做法.

1

那就对 $b$ 建立后缀自动机然后枚举起点然后上后缀自动机上跑即可. ### 2 $a$ 的一个最短的子串，它不是 $b$ 的子序列. 对 $b$ 建立子序列自动机,依然暴力 $n^2$ 跑即可. ### 3 $a$ 的一个最短的子序列，它不是 $b$ 的子串. 考虑分别在 $a$ 的子序列自动机上和 $b$ 的 SAM上一起跳. 令 $f_{i,j}$ 表示在 $i$ 的序列自动机跳到状态 $i$ , $b$ 的 SAM 上跳到 $j$ 时最多能添加几个字符且保证仍满足不是 $b$ 子串. 然后枚举是否有一个可行的转移即可. ### 4 $a$ 的一个最短的子序列，它不是 $b$ 的子序列. 同理上一问,只是换成 $a,b$ 都在子序列自动机上跑即可. [P4608 \[FJOI2016\]所有公共子序列问题](https://www.luogu.com.cn/problem/P4608) 使用第一种. 需要高精. 需要压位高精,普通高精会MLE. 下辈子就补上.