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

前言

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

本来想去写计算几何和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

\(a\) 的一个最短的子串,它不是 \(b\) 的子串.

那就对 \(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]所有公共子序列问题

使用第一种.

需要高精.

需要压位高精,普通高精会MLE.

下辈子就补上.

上一篇:1002 A+B for Polynomials (25分)


下一篇:京东 - 负反馈的pairwise方式强化学习 - Recommendations with Negative Feedback viaPairwise Deep Reinforcement Lea