spoj nsubstr Substrings (后缀自动机 模板题)

http://www.spoj.com/problems/NSUBSTR/en/

题意:

f[i]指长度为i的串出现次数的最大值。这里的不同出现指,可以有重复串,只要起始位置不同就视为不同的出现。

求f[1]..f[lenth]。

思路:

我们知道,SAM上的节点是right集合的等价类。

一个子串的right集合是指在一个母串中,某个子串所有出现位置的右端点的集合。

如果两个子串的right集合完全相同,那么就可以归结为同一个节点,也就是说这两个子串对于SAM是等价的。

因为在SAM上,这两个子串后,添加若干字符得到的后缀都是一样的。

所以一个SAM节点的个数,就是right集合等价类的个数(如果不考虑初始状态)

对于SAM某一个节点,其能表示的子串有一个范围,设为[MIN,MAX]

SAM的一个节点能表示的子串的含义是说,这些子串的right集合相同。

而一个子串出现的次数就是其right集合的大小。

考虑SAM上的某个节点,其表示的长度区间在[MIN,MAX]的子串都出现了|right|次

如果我们直接从MIN更新到MAX有点太暴力了,实际上这里我们可以只更新f[MAX]

由于长度i-1的子串出现的次数一定大于等于长度为i的子串出现的次数,所以最后长度从大到小更新f即可。

现在的问题就变成了如何求right集合。

实际上我们不需要知道right集合的具体组成,只需要知道right集合的大小。

考虑一棵parent树,树上某个节点的right集合就是该节点的所有儿子节点的right集合的并集

因此我们只需要在parent上自低向上更新right集合的大小就可以了。

如何保证在parent树上是自底向上更新呢?

我们只需要按照len,也就是SAM中所有节点能表示的子串的MAX值从大到小的顺序更新right集合。

原因是parent树上,儿子的len一定比父亲的len长。

注意到,对于parent树上的叶子节点,其right集合是1,这也是我们的初始状态。

部分实现细节见代码注释。

关于SAM的详细学习笔记日后补

20171109Update:

注释写错了一处,a[1]应该是len最短的状态的标号,之前写成了最长的。

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz