Suffix Automation!

Bouvardia纠结了好久的后缀自动机……

Overview
Definition
Properties
Construction
Samples

Overview

后缀自动机确实是个挺玄的东西呐. 是解决许多字符串问题强有力的工具.

顾名思义, 后缀自动机是能够识别一个字符串所有后缀的结构, 根据她的性质, 她同时可以识别一个字符串的所有字串.

Definition

定义超多的说…… Bouvardia也是翻来覆去研究了好久, 所以特意记在这里哦.

$trans(St, c)$ : 在状态 $St$ 后加入字符 $c$ 到达的状态.

$ST(str)$ : $trans(init, str)$, 从初始状态读入字符串 $str$ 后到达的状态.

$Suf$ : 字符串 $S$ 的后缀集合

$Fac$ : 字符串 $S$ 的连续字串集合

$Right(\alpha)$ : 字符串 $\alpha$ 在字符串 $S$ 中出现位置右端点的集合.

Properties

可以发现, 如果得到了 $Right(\alpha)$, 又得到了一个 $len$ , 我们就可以唯一确定一个字串.

那么我们不妨把所有 $Right$ 集相等的子串压缩到一个状态下, 这时她的合法 $len$ 就有了一个区间 $[Min, Max]$, 当长度小于$Min$ 时, $Right$ 集可能会扩大, 这不符合定义, 相对地, 长度大于 $Max$ 时, 由这个 $Right$ 集和这个 $len$ 确定的字串就不相等, 相应地 $Right$ 集也不相等.

所以一个状态的可行长度一定是一个连续区间.

考虑两个状态 $\alpha, \beta$, 有$Right(\alpha), Right(\beta)$, 记作$R_a, R_b$, 若$R_a \cap R_b = \gamma \not= \varnothing$.

由于$ST(\alpha) \not= ST(\beta)$根据定义, $str_a, str_b$ 没有交集. 由于 $ \gamma \not= \varnothing$ , 所以$[Min(\alpha), Max(\alpha)] \cap [Min(\beta), Max(\beta)] = \varnothing$.

不妨设 $Max(\alpha) < Min(\beta)$, 那么状态$\alpha$表示的所有串都比$\beta$的短. 所以对于从 $\gamma$向前的所有可表出串, $\alpha$ 都是 $\beta$ 的后缀, 又根据$Right$集合的定义, 会有所有$\alpha$ 中的元素跟随$\beta$作为后缀出现. 那么, 在每个 $p \in Right(\beta)$ 向前的串, $\alpha$ 都是 $\beta$ 的后缀, 即 $R_a \subset R_b$.

所以, 我们有:

$\begin{cases}R_u \subset R_v, & \text{$u$ suffix $v$}\ R_u \cap R_v = \varnothing, & \text{otherwise.}\end{cases}$

由于$Right$ 集合只有包含和不交关系, 这种关系实际构成了一颗树.

我们定义一颗$Parent$树, 则状态$s$在树上的直接父亲一定是满足$R_s \subset R_{fa}$中$| R | $最小的一个节点.

根据上面对$Min$的说明, 当长度为$Min - 1$时, $R$集合一定进入了父亲的范围, 并且是首次进入, 所以我们有:

$Max(fa) = Min(s) - 1$

定义状态$NULL$ 为不存在 $trans(init, str)$ 到达 $ST(str)$. 反过来, 一个串$str$是$S$的字串当且仅当在 $SAM_S$ 中, $ST(str) \not= NULL$.

而一个字串的出现次数就是她所在状态$Right$集合的大小.

实际应用中我们通常不直接求出每个状态的$Right$ 集, 根据定义, 一定有:

$Right_s = \bigcup_{y \in son(s)}{Right_y}$

所以利用DFS序的子树连续区间性质可以解决一些子串位置问题.

最后一个证明, 根据定义, 对于一个有限长度字符串$S$, $SAM_S$ 可以识别的串一定是有限个, 也即对于任意一个状态$ST(str)$, 不存在一种$trans(ST(str), str’)$, 使得$trans(ST(str), str’) = ST(str), | str’ | \not= 0$, 否则$| S | = \infty$, 与条件矛盾.

那么, 将 $trans$ 视作边, 则SAM是一个DAG.

Construction

对于当前字符串 $T$, 新加入字符 $c$, 我们要

$SAM_T$ $\rightarrow SAM_{Tc}$

添加字符后, 我们得到了一些新的子串, 她们一定是$Tc$的后缀, 而这些后缀一定是在 $T$的后缀后面添加一个 $c$.

定义$T$的右端点 $Q$, 考虑所有能表示$T$的后缀的节点 $v_1, v_2, v_3, \ldots$, 由于一定存在一个节点$P$, 使得$Right(P) = \{L\}$, 所以$v_1, v_2, v_3, \ldots$ 在 $Parent$ 树上一定是 $P$ 的祖先.

插入字符后, 新建一个节点$nP = ST(Tc)$, 则$Right(nP) = \{Q + 1\}$. 不妨按照从后代到祖先的顺序定义: $v_1 = P, v2, \ldots, v_k = root$.

对于每个$v$, 若$Right(v)$中除不考虑 $r_n = Q$ 外没有符合要求的元素, 则连一条边 $\begin{align}v \xrightarrow{c} nP \end{align}$, 这是这个状态首次可以转移到结尾为$c$的状态.

再考虑 $v_p$为 $1 \ldots k$ 中第一个有标号为 $c$ 的边的状态. 不考虑$r_n$, 令$q = trans(v_p, c)$, 那么$Right(q) = \{r_i + 1| T_{r_i + 1} = c\} $ , 但是我们不能直接在 $Right(q)$ 中添加一个元素 $Q + 1$.

例如对于一个 $v_p$, 长度为 $Max(v_p)$的串:

AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx

而对于$q$, 长度为$Max(q)$的串:

AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx

如果在她的 $Right$ 集中插入 $Q + 1$, 则修改了$Max(q)$, 这是错误的.

当然, 如果恰好有 $Max(q) = Max(v_p) + 1$, 即我们可以直接在一个字串后连接一个字符$c$来转移到q状态, 那么在整个$T$后连接一个当然也是合法转移. 所以直接令$Parent(nP) = q$ 即可.

继续考虑当前状态. 我们可以新建一个节点 $nQ$, 使得$Right(nQ) = Right(q) \cup \{Q + 1\}$, 这个新节点是可以通过$v_p$直接连接一个$c$得到的, 所以$Max(nQ) = Max(v_p) + 1$.

那么一定有 $Right(q) \subset Right(nQ)$, 故新的 $Parent(q) = nQ$, 同时因为 $nQ$ 是我们目前有的第一个包含了${Q + 1}$ 和其他元素的节点, 故$Parent(nP) = nQ$. 又因为 $Right(q) \subset Right(Parent(q)_{former}) $, 新的$nQ$节点能表示的串一定是$q$能表示的串的一个后缀, 不会越过范围表示其他的串, 所以她可以继承$q$的真子集特性, 那么$Parent(nQ) = Parent(q)_{former}$. 同时后缀这个性质还可以帮助我们得出, $trans(nQ) = trans(q)$.

最后, 我们处理原来转移到 $q$ 的一段$v$节点, 在添加新字符后, 她们实际可以转移到的状态较 $q$ 扩充了, 所以将 $q$ 替换为 $nQ$ 即可.

至此, SAM的扩展操作就全部完成啦, 按顺序扩展就可以建出整个字符串的SAM！

结合代码食用喵~

struct SuffixAutomation
{
	int tr[maxn][26], fa[maxn], mx[maxn];
	int lst, cnt;
	void Insert(int c)
	{
		int p = lst, np = ++cnt;
		lst = np; mx[np] = mx[p] + 1;
		for(;p && !tr[p][c]; p = fa[p]) tr[p][c] = np;
		if(!p) fa[np] = 1;
		else
		{
			int q = tr[p][c];
			if(mx[p] + 1 == mx[q]) fa[np] = q;
			else
			{
				int nq = ++cnt;mx[nq] = mx[p] + 1;
				memcpy(t[nq].tr, t[q].tr, sizeof(t[q].tr));
				fa[nq] = fa[q]; fa[q] = fa[np] = nq;
				for(; tr[p][c] == q; p = fa[p]) tr[p][c] = nq;
			}
		}
		siz[np] = 1;
	}
}

Samples

Luogu 3804

Description

给定一个字符串，求其出现次数 × 长度的最大值。

Solution

根据Parent树的特性，按Right集大小做基数排序，倒序累加，一定可以保证儿子的贡献累加到父亲上。而在相同次数下，能产生贡献的一定是最长串，所以用$siz_x \times Max(x)$ 更新答案就好啦。

Code

//in struct SuffixAutoMation:	
	void build()
    {
        scanf("%s", str + 1); n = strlen(str + 1);
        lst = cnt = 1;
        for(int i = 1; i <= n; ++i)
            Insert(str[i] - 'a');
    }
    void solve()
    {
        for(int i = 1; i <= cnt; ++i) bkt[mx[i]]++;
        for(int i = 1; i <= cnt; ++i) bkt[i] += bkt[i - 1];
        for(int i = 1; i <= cnt; ++i) arr[bkt[mx[i]]--] = i;
        for(int i = cnt; i; --i)
        {
            int cur = arr[i];
            siz[fa[cur]] += siz[cur];
            if(siz[cur] > 1) ans = max(ans, (ll)siz[cur] * (ll)mx[cur]);
        }
        printf("%lld\n", ans);
    }

Luogu 1368

Description

求一个字符串循环同构串中字典序最小的串.

Solution

把字符串在SAM上插入两遍, 从根节点开始每次选最小的转移边转移, 直到转移n次.

字符集比较大, 用map.

struct SuffixAutoMation
{
    map<int, int> tr[maxn];
    int fa[maxn], mx[maxn];
    int lst, cnt;
    void Insert(int c)
    {
        int p = lst, np = ++cnt;
        lst = np; mx[np] = mx[p] + 1;
        for(; p && !tr[p].count(c); p = fa[p]) tr[p][c] = np;
        if(!p) fa[np] = 1;
        else
        {
            int q = tr[p][c];
            if(mx[p] + 1 == mx[q]) fa[np] = q;
            else
            {
                int nq = ++cnt; mx[nq] = mx[p] + 1;
                tr[nq] = tr[q];
                fa[nq] = fa[q]; fa[q] = fa[np] = nq;
                for(; tr[p][c] == q; p = fa[p]) tr[p][c] = nq; 
            }
        }
    }
    void build()
    {
        scanf("%d", &n);
        lst = cnt = 1;
        for(int i = 1; i <= n; ++i)
            str[i] = rd();
        for(int i = 1; i <= n; ++i) Insert(str[i]);
        for(int i = 1; i <= n; ++i) Insert(str[i]);
    }
    void solve()
    {
        int now = 1;
        for(int i = 1; i <= n; ++i)
        {
            printf("%d ", tr[now].begin()->first);
            now = tr[now].begin()->second;
        }
    }
}SAM;

BZOJ 4032

Description

在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。

一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。

一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。

下面，给两个小写字母串A，B，请你计算：

(1) A的一个最短的子串，它不是B的子串

(2) A的一个最短的子串，它不是B的子序列

(3) A的一个最短的子序列，它不是B的子串

(4) A的一个最短的子序列，它不是B的子序列

Solution

我们可以$O(n^2)$地建出一个序列自动机.

好吧其实这就是暴力的说.

也就是贪心地匹配子序列的转移.

对于每个问题在相应的自动机上跑BFS就好啦.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <bitset>

using namespace std;

const int maxn = 2005;

char a[maxn], b[maxn];

struct SuffixAutomation
{
	int tr[maxn << 1][26], mx[maxn << 1], fa[maxn << 1];
	int lst, cnt;
	SuffixAutomation()
	{
		lst = cnt = 1;
	}
	void Insert(int c)
	{
		int p = lst, np = ++cnt;
		lst = np; mx[np] = mx[p] + 1;
		for(; p && !tr[p][c]; p = fa[p]) tr[p][c] = np;
		if(!p) fa[np] = 1;
		else
		{
			int q = tr[p][c];
			if(mx[p] + 1 == mx[q]) fa[np] = q;
			else
			{
				int nq = ++cnt; mx[nq] = mx[p] + 1;
				memcpy(tr[nq], tr[q], sizeof(tr[q]));
				fa[nq] = fa[q]; fa[q] = fa[np] = nq;
				for(; tr[p][c] == q; p = fa[p]) tr[p][c] = nq;
			}
		}
	}
}sama, samb;
struct SeqAutomation
{
	int tr[maxn][26], lst[26], pre[maxn];
	int cnt;
	SeqAutomation()
	{
		cnt = 1;
		for(int i = 0; i < 26; ++i) lst[i] = 1;
	}
	void Insert(int c)
	{
		int np = ++cnt;
		pre[np] = lst[c];
		for(int i = 0; i < 26; ++i)
		{
			for(int j = lst[i]; j && !tr[j][c]; j = pre[j])
				tr[j][c] = np;
		}
		lst[c] = np;
	}
}seqa, seqb;
struct node
{
	int a, b, len;
	node(int a_ = 0, int b_ = 0, int l = 0):
		a(a_), b(b_), len(l){};
};
bitset<maxn << 1> vis[maxn << 1];

inline void sam_sam()
{
	queue<node> q;
	q.push(node(1, 1, 0));
	vis[1][1] = 1;
	while(!q.empty())
	{
		node u = q.front(); q.pop();
		for(int i = 0; i < 26; ++i)
		{
			int ya = sama.tr[u.a][i], yb = samb.tr[u.b][i];
			if(ya && yb)
			{
				if(vis[ya][yb]) continue;
				q.push(node(ya, yb, u.len + 1));
				vis[ya][yb] = 1;
			}
			if(ya && !yb) {printf("%d\n", u.len + 1); return;}
		}
	}
	puts("-1");
	return;
}
inline void sam_seq()
{
	queue<node> q;
	for(int i = 0; i < (maxn << 1); ++i) vis[i].reset();
	q.push(node(1, 1, 0));
	vis[1][1] = 1;
	while(!q.empty())
	{
		node u = q.front(); q.pop();
		for(int i = 0; i < 26; ++i)
		{
			int ya = sama.tr[u.a][i], yb = seqb.tr[u.b][i];
			if(ya && yb)
			{
				if(vis[ya][yb]) continue;
				q.push(node(ya, yb, u.len + 1));
				vis[ya][yb] = 1;
			}
			if(ya && !yb) {printf("%d\n", u.len + 1); return;}
		}
	}
	puts("-1");
	return;
}
inline void seq_sam()
{
	for(int i = 0; i < (maxn << 1); ++i) vis[i].reset();
	queue<node> q;
	q.push(node(1, 1, 0));
	vis[1][1] = 1;
	while(!q.empty())
	{
		node u = q.front(); q.pop();
		for(int i = 0; i < 26; ++i)
		{
			int ya = seqa.tr[u.a][i], yb = samb.tr[u.b][i];
			if(ya && yb)
			{
				if(vis[ya][yb]) continue;
				q.push(node(ya, yb, u.len + 1));
				vis[ya][yb] = 1;
			}
			else if(ya && !yb) {printf("%d\n", u.len + 1); return;}
		}
	}
	puts("-1");
	return;
}
inline void seq_seq()
{
	for(int i = 0; i < (maxn << 1); ++i) 
		vis[i].reset();
	queue<node> q;
	q.push(node(1, 1, 0));
	vis[1][1] = 1;
	while(!q.empty())
	{
		node u = q.front(); q.pop();
		for(int i = 0; i < 26; ++i)
		{
			int ya = seqa.tr[u.a][i], yb = seqb.tr[u.b][i];
			if(ya && yb)
			{
				if(vis[ya][yb]) continue;
				q.push(node(ya, yb, u.len + 1));
				vis[ya][yb] = 1;
			}
			else if(ya && !yb) {printf("%d\n", u.len + 1); return;}
		}
	}
	puts("-1");
	return;
}

int main()
{
	scanf("%s", a);
	scanf("%s", b);
	int la = strlen(a), lb = strlen(b);
	for(int i = 0; i < la; ++i) sama.Insert(a[i] - 'a');
	for(int i = 0; i < lb; ++i) samb.Insert(b[i] - 'a');
	for(int i = 0; i < la; ++i) seqa.Insert(a[i] - 'a');
	for(int i = 0; i < lb; ++i) seqb.Insert(b[i] - 'a');
	sam_sam();
	sam_seq();
	seq_sam();
	seq_seq();
	return 0;
}

Suffix Automation!

Table of Contents

Overview

Definition

Properties

Construction

Samples

Luogu 3804

Description

Solution

Code

Luogu 1368

Description

Solution

BZOJ 4032

Description

Solution

Bouvardia.L