【算法竞赛学习笔记】后缀自动机SAM | 您所在的位置:网站首页 › ACM算法竞赛没用 › 【算法竞赛学习笔记】后缀自动机SAM |
title : 后缀自动机 date : 2021-11-11 tags : ACM,字符串 author : Linno 前置知识KMP,Trie,AC自动机等字符串基础 DFA(有限状态自动机) 后缀自动机(Suffix automaton ,SAM) 定义字符串s的SAM是一个接受s的所有后缀的最小DFA(确定性有限自动机)。直观上SAM是给定字符串的所有字串的压缩形式。而构造的时间复杂度和空间复杂度仅为 O ( n ) O(n) O(n)。一个SAM最多有2n-1个节点和3n-4条转移边。 符号定义endpos(t)为字符串s中t的所有结束位置,endpos的集合即为SAM的状态集 subs(sta):SAM中sta状态所包含的所有子串的集合 mxsub(sta):sta状态所包含的子串中最长的子串 mnsub(sta):sta状态所包含的子串中最短的子串 sz[i]:sta表示的endpos集合大小,即i号点字符串集合在整个串出现次数 nxt(sta):sta遇到的下一个字符集合 link(sta): 性质状态数:不超过2n-1 转移数:不超过3n-4 D A G 性 质 DAG性质 DAG性质:SAM是有向无环图,因此可以用DP计算路径条数。 状态集:所有endpos的集合即为SAM的状态集。 转移函数n x t ( s t a ) = { S [ i + 1 ] ∣ i ∈ e n d p o s ( s t a ) } nxt(sta)=\{S[i+1]|i\in endpos(sta)\} nxt(sta)={ S[i+1]∣i∈endpos(sta)} t r a n s ( s t a , c ) = { x ∣ m x s u b ( s t a + ( c ∈ s u b s ( x ) ) } trans(sta,c)=\{x|mxsub(sta+(c\in subs(x))\} trans(sta,c)={ x∣mxsub(sta+(c∈subs(x))} 后缀链接linksta状态链接到下一个连续后缀所在的状态,叫做后缀链接。 子串表示法用一个点的集合以及长度len来描述一个子串 Parent树 引理1两 个 非 空 子 串 u 和 w ( 假 设 ∣ u ∣ ≤ ∣ w ∣ ) 的 e n d p o s 相 同 , 当 且 仅 当 字 符 串 u 是 w 的 后 缀 。 两个非空子串u和w(假设|u|\leq|w|)的endpos相同,当且仅当字符串u是w的后缀。 两个非空子串u和w(假设∣u∣≤∣w∣)的endpos相同,当且仅当字符串u是w的后缀。 对于任意一个状态 s t a sta sta,任取 s t r ∈ s u b s ( s t a ) str\in subs(sta) str∈subs(sta),都有 s t r str str是 m x s u b ( s t a ) mxsub(sta) mxsub(sta)的后缀。 例如:subs(7)={aabbab,abbab,bbab,bab} 任取一个字符串str,str是mxsub(7)=aabbab的后缀。 SAM中一个状态所包含的子串的集合是由长度连续的一系列字符串构成,并且由长到短,依次减少最前面的字符。 引理2两个非空子串u和w(假设 ∣ u ∣ ≤ ∣ w ∣ |u|\leq|w| ∣u∣≤∣w∣),要么 e n d p o |
CopyRight 2018-2019 实验室设备网 版权所有 |