$后缀自动机(SAM)$
$定义$
如图,有$1$个起点$S$,每$1$条边代表$1$个字符,从$S$出发的所有路径(指蓝边)都对应了原串的$1$个子串
所有蓝边构成$1$个有向无环图(拓扑图),所有绿边构成$1$棵树
节点个数为线性
$性质$
定义节点$i$对应的字符串为自动机中从节点$S$出发到$i$的最长路径
$endpos(i)$ 表示为节点$i$对应字符串在原串中匹配成功时的所有末尾下标集合
则有以下性质:
-
令 $s1$,$s2$ 为 $S$ 的两个子串 ,不妨设 $|s1| \leq |s2|$ (我们用$|s|$表示 $s$ 的长度 ,此处等价于$s1$ 不长于$s2$)。则$s1$ 是 $s2$ 的后缀当且仅当 $endpos(s1)⊇endpos(s2)$ ,$s1$ 不是 $s2$ 的后缀当且仅当 $endpos(s1)∩ endpos(s2)=∅$ 。
-
两个不同子串的$endpos$,要么有包含关系,要么没有交集。
-
两个子串的$endpos$相同,那么短串为长串的后缀。
-
对于一个状态 $st$ ,以及任意的 $longest(st)$ 的后缀 $s$ ,如果 $s$的长度满足:$|shortest(st)|≤|s|≤|longsest(st)|$ ,那么 $s∈substrings(st) $
对于节点$i$,有$len$,$fa$,$ch[]$
$len$ 表示为从节点$S$出发到$i$的最长路径长度
$fa$ 表示为$endpos$包含$i$,且$endpos$与$i$最接近的点,即绿边
$ch[]$ 表示为从$i$出发的边,即蓝边
$构造$
void extend(int c)
{
int p = last, np = last = ++ tot;
node[np].len = node[p].len + 1;
for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
if (!p) node[np].fa = 1;
else
{
int q = node[p].ch[c];
if (node[q].len == node[p].len + 1) node[np].fa = q;
else
{
int nq = ++ tot;
node[nq] = node[q], node[nq].len = node[p].len + 1;
node[q].fa = node[np].fa = nq;
for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
}
}
}