本地东莞网站建设,用asp.net开发网站的优势,长沙科技公司排名,用py做网站写在前面
后缀自动机#xff0c;简称SAMSAMSAM,是一种十分优秀的字符串匹(shu)配(ju)算(jie)法(gou)
字符串界的bossbossboss#xff0c;几乎可以解决全部正常的字符串题目
至少我前前后后学了一年#xff0c;听过444次课#xff0c;几度怀疑自己不适合oioioi
请做好心…写在前面
后缀自动机简称SAMSAMSAM,是一种十分优秀的字符串匹(shu)配(ju)算(jie)法(gou)
字符串界的bossbossboss几乎可以解决全部正常的字符串题目
至少我前前后后学了一年听过444次课几度怀疑自己不适合oioioi
请做好心理准备
定义
有限状态自动机
不管可以理解为有向图。
唯一的区别是信息储存在边上每个点有字符集个数的转移到若干其他点类比字典树。
如果对于一个字符串沿着每个点的转移走如果不出界称该自动机可以表示这个字符串。
以下将“点”称为状态
能干啥
后缀自动机能表示母串的所有子串。
算法流程
首先明确一点子串规模是O(N2)O(N^2)O(N2)的
所以一个状态必须表示多个子串
也就是说我们要定义出等价的子串
对于一个子串SSS定义endpos(S)endpos(S)endpos(S)为SSS在原串中所有出现的结束位置的集合
每个状态与一个endposendposendpos集合一一对应。即一个状态表示一个endposendposendpos集合。
需要注意的是endposendposendpos是完全虚构的在代码中不会出现。
然后可以表示所有endposendposendpos等于它的字符串称这些子串为一个endposendposendpos等价类
转移
此时我们定义转移为这个类所有串加上这个字符后所在的转移。
一个类的同一个转移是相同的因为向ccc的转移的本质是当前endposendposendpos整体后移一位的所有ccc的位置。
感性理解。
两个性质
1.两个子串S1,S2S_1,S_2S1,S2满足S1S_1S1是S2S_2S2的后缀当且仅当endpos(S2)⊆endpos(S1)endpos(S_2)\subseteq endpos(S_1)endpos(S2)⊆endpos(S1)
S2S_2S2出现的地方一定有S1S_1S1出现但有S1S_1S1出现的地方不一定有S2S_2S2
2.一个等价类中的子串均为该类中最长串的后缀且长度连续
第一个显然
对于一个串SSS若有后缀S1S_1S1长度小于SSS,且S1S_1S1和SSS是等价类
设S2S_2S2为长度在它们之间的后缀
有endpos(S)⊆endpos(S2)⊆endpos(S1)endpos(S) \subseteq endpos(S_2) \subseteq endpos(S_1)endpos(S)⊆endpos(S2)⊆endpos(S1)
因为endpos(S)endpos(S1)endpos(S)endpos(S_1)endpos(S)endpos(S1)
所以endpos(S)endpos(S2)endpos(S1)endpos(S) endpos(S_2) endpos(S_1)endpos(S)endpos(S2)endpos(S1)
说明它们之间的串都是一个等价类
Parent链
由于类中的长度只有一段逼死强迫症
所以我们定义每个状态SSS的failfailfail指针
满足endpos(S)∈endpos(fail(S))endpos(S) \in endpos(fail(S))endpos(S)∈endpos(fail(S))
且fail(S)fail(S)fail(S)要尽量靠后
可以理解为从一个状态沿failfailfail往上跳取出该类中的所有串你将会见证这个串不断失去第一个字符不断变为后缀最后变成空串。我们称这条链为parentparentparent链。
先放个图以AABAABAAB为栗子 可能看不出啥但有个大概印象吧
构造算法
SAM 采用增量算法即一个一个字符插入
这使得 SAM 擅长处理动态问题
现在假设插入第iii个字符前i−1i-1i−1个的 SAM 已经建立好
首先上一个插入的点是整个串所在的状态记为ppp
新建一个节点记为curcurcur。显然curcurcur最长的长度为当前串的长度。
由于其他子串已经处理了我们要做的就是搞出当前串的后缀
此处分333种情况
①最简单的情况
栗子AA\texttt {AA}AA插入B\texttt BB 此时curcurcur是{3}\{3\}{3}
由于每个类里的字符串是等价的感性理解
我们可以找到旧的串的所有后缀给它加上新的字符
也就是让ppp沿着failfailfail不断跳令ch[p][S[i]]curch[p][S[i]]curch[p][S[i]]cur
即原来的所有后缀加上新来的字符就成了新的后缀 最后fail(cur)1fail(cur)1fail(cur)1完结撒花 ②然而这只是最简单的情况
栗子AA\texttt {AA}AA插入A\texttt AA 没区别 咦已经有转移了呀
说明什么
说明现在新串的这个后缀已经在之前的串中出现了
那这个后缀的后缀也一定出现了
请摆脱这个栗子
记qch[p][S[i]]qch[p][S[i]]qch[p][S[i]]
上面的话翻译一下ppp表示的串S[i]S[i]S[i]已经出现了
而这个玩意就是qqq
……吗
ppp的最长串S[i]S[i]S[i]一定在qqq上(定义)但不一定是qqq最长的
先讨论是最长的的情况
yyyyyy一下我们要找的后缀不就是qqq的最长串吗
而这个后缀的后缀也就是我们后面要找的就在qqq的parentparentparent链上
这么说来我们令fail[cur]qfail[cur]qfail[cur]q就好了 over
③然而还有个最复杂的情况
也就是上面的不是qqq最长的
栗子AAB\texttt{AAB}AAB加B\texttt BB 走程序 停
此时的qqq有B,AB,AAB\texttt {B,AB,AAB}B,AB,AAB
而我们的curcurcur只想要B\texttt BB和链上的东西
怎么办
拆了呗 记新建的点为q′qq′
维护信息
首先curcurcur要的是q′qq′和qqq祖先上的 然后我们发现qqq和q′qq′有后缀关系 接下来维护转移
q和q′q和qq和q′是同一个分出来的而它们原来的转移共同构成了后面的状态
现在它们拆开了理应维护好后面
即将qqq的转移拷贝给q′qq′ 考虑这样的事实在前面某个位置原来转移到了这个状态。现在这个状态分了需要考虑具体转移到哪一边。
注意到转移到q′qq′而不转移到qqq当且仅当这个状态最长串长小于q′qq′最长串长。
并且都是qqq去掉末尾的一个字符后的后缀
根据意识流这样的状态最后面的满足的刚好是ppp
而剩下的都在ppp的parentparentparent链上
即跳ppp的parentparentparent链如果有到qqq的转移将它改到q′qq′
因为是后缀所以一定是S[i]S[i]S[i]的转移因为ch[p][S[i]]qch[p][S[i]]qch[p][S[i]]q
至此SAM 就构造完毕了
复杂度是O(N)O(N)O(N)的显然我不会证
代码
具体实现的时候每个节点只记录最长串的长度lenilen_ileni
int fa[MAXN],ch[MAXN][26];
int len[MAXN],last1,tot1;
int siz[MAXN],a[MAXN],c[MAXN];
void insert(int c)
{int plast,curtot;len[cur]len[last]1;lastcur;for (;p!ch[p][c];pfa[p]) ch[p][c]cur;//跳failif (!p) fa[cur]1;//情况1else{int qch[p][c];if (len[p]1len[q]) fa[cur]q;//情况2else//情况3{int clonetot;len[clone]len[p]1;for (int i0;i26;i) ch[clone][i]ch[q][i];fa[clone]fa[q];fa[q]fa[cur]clone;for (;ch[p][c]q;pfa[p]) ch[p][c]clone;} }
}运用
劈配子串
按照定义沿着转移走
最长公共子串
建出SSS的后缀自动机拿TTT去跑
不断用lenilen_ileni更新答案
如果走不动了就跳failfailfail
处理出现次数
对于每一次插入一个类出现次数增加当且仅当这是当前的后缀
也就是把这个点的parentparentparent链都111
显然会TTT。于是先建完按长度瞎排个序倒着往上推。
这样sizisiz_isizi表示状态iii中的一个串的出现次数。显然它们是一样的。
应该是用的最多的。
void query()
{for (int i1;itot;i) c[len[i]];for (int i1;in;i) c[i]c[i-1];for (int i1;itot;i) a[c[len[i]]--]i;for (int itot;i1;i--) siz[fa[p]]siz[p];
}然后你就可以处理各种沙雕的字符串题
本质不同的串的个数
由于一个串只会被表示一遍
我们相当于求所有状态表示的串的个数之和。
即∑(len[p]−len[fa[p]])\sum( len[p]-len[fa[p]])∑(len[p]−len[fa[p]])
Link Cut Tree维护parent链
先写到这里吧想到再补。
