后缀自动机小结②

【cxjyxx_me是个大沙茶 他连后缀自动机这个pj算法都不会。。】
后缀自动机的应用 我觉得最重要的是要知道这些性质:
①所有的子串都能由起始点走到
②加入前缀#后 在fail树上的叶子代表串各不相同 且共同组成串s的所有前缀
③从起始点走到所有”接受态点”的所有路径各不相同 且共同构成串s的所有后缀
[注:所谓接受态点 即last点及其所有祖先 即 last t[last].f t[t[last].f].f……..]

知道这几个性质感觉就所向披靡了~~
这里就讲一下clj课件里提到的题目吧<这些题我大多没写过。。只是讲下思路>
——————————–
最小循环串

给一个字符串S,每次可以将它的第一个字符移到最后面,求这样能得到的字典序最小的字符串。
——————————-
好吧这里的题目是直接copyCLJ的课件的。。所以字体有点奇葩、、 不要在意细节~~
这题其实是后缀数组的题啊= =
只要把s copy一个接在s的后面
求出最小的 起始点<=原s的length的后缀
这里顺便讲下怎么用sam线性构造sa吧
其实很简单 做一次dfs 对于一个节点 从它的ch[0]开始循环即可
然后如果到达一个接受态点即可吧当前串(可以用这个串的长度表示) 加入sa[]数组
因为按这样的循环方式进行dfs可以保证串的值是递增的 这个很显然
最后就可以得到sa数组了~
线性!
——————————-

SPOJ NSUBSTR
给一个字符串S,令F(x)表示S的所有长度为x的子串中,出现次数的最大值。求F(1)..F(Length(S))

——————————-
在fail树上 我们定义叶子节点的权值为1 其他节点权值为0
对于一个节点所代表串的出现次数就是以这个节点为根的子树权值和
为什么是这样呢?
我们知道每个叶子代表了一个前缀
且对于一个节点的代表串 一定是其子孙节点代表串的后缀
那么他的子孙中有几个是前缀就代表了这个节点的代表串出现了几次
然后对于每个节点i 用它的子树权值和去更新F(t[i].l)
最后再用每个F(i) 去更新F(i – 1)即可
为什么是对的?
这不是很显然么= =
一个长度是k的串出现了x次 那么它的长度为1~k的子串一定最少也可以出现x次- –
——————————-
BZOJ2555 SubString
——————————-
【因为这题是bzoj的 所以我有做(毫无节操- -)、后面的题解会写 这里就不写了】
——————————-
SPOJ SUBLEX
给一个长度不超过90000的串S,每次询问它的所有不同子串中,字典序第K小的,询问不超过500个。
———————————-
我们知道sam从起点开始走
可以走到所有子串
对于一个点i 它能走到的节点个数(一个节点以不同路径被走两次算两次)就代表了以它为前缀的子串个数
所以我们可以求出所有i的能走到的节点个数 记在num数组里
如果num[t[i].ch[0]] >= k那么就走到t[i].ch[0]否则k-= num[t[i].ch[0]] 然后循环下一个ch[1]
这个过程可以类比在平衡树上找k大
———————————-
还有两题LCS就不写了 【太难了不能直视(大雾】
END
然后等等放几题我刷的题的题解。。

后缀自动机小结②》上有1条评论

发表评论