BZOJ 2780 / SPOJ JZPGYZ Sevenk Love Oimaster

题意

给出一系列的字符串,我们把这些串叫母串,然后给你若干字符串,对于每一个字符串,你要求出在多少个母串中可以找到和给出的字符串相同的母串的字串。

思路

子串问题,要借助后缀系列解决,这个题使用了后缀自动机。但是通常意义的后缀自动机都是针对一个母串建立的,现在我们手里有一堆母串,这时候就需要我们进行活用,来创建“广义后缀自动机”,这个自动机将可以接受母串集合里所有的字串。

广义后缀自动机的建立方法其实是在一般的自动机创建基础之上,增加了一些东西。构造后缀自动机的方法是增量法,构造广义后缀自动机的方法也是一样的,但是我们从第个二串开始,一位一位增量的时候,我们有可能会用到构造到一半的自动机的某些节点或者某些转移边。对于当前将要加入的mxn(最长可接受字串长度)值,和当前追加节点时的last,如果last有一条转移边可以用,而且即将加入的新节点的mxn值正好等于last的mxn+1,这说明既存的节点和我们将要加入的节点是等价的,这一轮的追加到这里就可以结束了。如果存在转移边,但是转移边连着的节点mxn值并不是last的mxn+1,这个时候就需要我们使用在平常构造后缀自动机中使用的“拆点”方法。复制既存的节点作为符合我们mxn要求的节点,调整parent关系和所有自动机上父亲节点的转移关系,就像我们在平常构造自动机时为了防止mxn异常缩短采用的“拆点”方法一样。如果last节点不存在可用的转移边,这时候按照普通的增量法处理就可以。(如果觉得费解,不妨直接参考我的MultiSAM_Append()方法)。

创建完广义后缀自动机,这还只是个开始。接下来我们要提取出自动机中的所有的parent关系,创建parent树。我们注意到,在parent树中,一个节点的子树代表的是以这个节点为后缀的全部字串。举个例子就是,对于“banana”的”ana”代表节点(mxn值3),他的子树就代表了”ana“,”nana“,”bana“,”anana“,”banana“,这一系列字串。这一特性有什么用呢?

注意到题意,我们要找到给出的串在多少个串中匹配,如果我们按照正常的方法在广义后缀自动机上完整地匹配这个串(如果匹配有中断,那就说明这个串不存在于母串集合的字串当中),这个时候转移到的最终状态对应节点的parent树的子树,就是在母串集合中所有的以给出的串为后缀的字串。如果我们给parent树上的每一个节点挂一个列表,标记这个节点都被哪些字符串利用了,这样只要我们逐一统计子树中的每一个节点,就可以知道当前给出的串在几个母串中存在,问题就可以解决了。

但是对于每一棵子树都统计一次,复杂度很大,显然需要再优化。优化的方法就是“DFS序把树压平”然后“离线处理”。首先遍历parent树,纪录每一个节点进入时的DFN和出去时的DFN,从进去到出去这两个DFN之间的所有节点(包括出入两个节点)显然就是parent的子树了。现在我们的问题就转变为了在某个数组上一段给定的区间求有多少个不同的数字,而且还是离线处理,这种问题可以使用一种O(n)的处理方法,详情可以参考BZOJ 1878 HH的项链

问题到了这里,终于是完美地解决了。

 

代码

 

SPOJ SUBLEX Lexicographical Substring Search

题意

把一个字符串所有的不同的字串全拿出来,按字典序排序,第k小的字符串是什么样子的呢?

思路

字串问题当然是后缀自动机了。对于给出的字符串,建立一个后缀自动机,然后对后缀自动机对应的状态图进行一次拓扑排序,每个节点的深度就是节点上携带的mxn(当前状态对应的字串最长为多少位)。接下来我们从深度最大的节点开始往根部处理每一个节点,我们要求出的就是对于每个能走的边,所有接下来的以这条边对应的字母开头的字串数目,而节点上面存的是节点出边的边权之和。这样我们就得到了一个处理好的图,我们只要在这个图上面搜索,逼近k值就可以了。

因为SPOJ卡常数特别严重,所以拓扑排序要使用计数排序的方法,而且要开额外的数组纪录每一个节点所有的孩子来加快之后的搜索速度。

代码

 

SPOJ LCS Longest Common Substring

[等待填坑]

 

SPOJ LCS2 Longest Common Substring II

[详细题解等待填坑]

SPOJ真是业界奇葩

 

Scroll to top