您好、欢迎来到现金彩票网!
当前位置:老k棋牌 > 栈自动机 >

NOI2018 你的名字 后缀自动机_线段树合并_可持久化

发布时间:2019-06-19 23:39 来源:未知 编辑:admin

  这部分相对好做一些,不过思维难度对我来说已经不小。但是一旦解出这一部分之后离满分算法就不远了。

  我们想求 $T$ 中出现的子串且在 $S$ 中未出现的种类(即重复的只算一个)。

  直接求未出现的种类似乎有些苦难,我们这么考虑:先求出 $T$ 中的所有种类,再减掉与 $S$ 重合的部分,这样似乎能好做一些。

  我们可以将 $T$ 串在 $S$ 的后缀自动机上跑一遍,每新加入一个字符就沿着转移边和适配边走。成功转移,就让记录匹配长度的计数器++,否则就让计数器等于失配节点的最长长度(这里一定是最长)。 这样,对于 $T$ 中的每个下标,我们能求出它的后缀再 $S$ 中以子串出现的最长长度。将 $T$ 中下标为 $i$ 的最长匹配后缀设为 $mx[i]$。

  确实是类似的。为了使统计不出现重复,我们可以再 $T$ 的后缀自动机上进行统计(因为后缀自动机上每个节点表示的字符串集合都是互不相同的)

  考虑一下后缀自动机插入的过程:新加入的 $np$ 节点的 $dis$ 就是等于该字符再原字符串中出现的位置,$nq$ 出现的位置应该与 $q$ 是相同的(原先 $nq$ 是被 $q$ 所包含的,即原先应该相同,新加入也必相同)。我们可以由此得到每个节点第一次在原字符串(即 $T$ ) 中出现的位置。那么,也就是说后缀自动机上每个节点都可以代表原串的某个后缀。而该节点所代表的后缀个数就是 $dis[p]-dis[f[p]]$。

  说到这里,我们将这个和之前的 $mx[i]$ 联系起来,一个点产生的贡献其实就是 $dis[i]-max(dis[f[i]],mx[pos[i]])$ 其中,$pos$ 数组为前文所说该节点对应的原字符串中出现的位置。 而我们取 $max$ 是因为有可能该贡献不由点 $p$ 记录,而是由 $p$ 在后缀中的父亲所记录。 当然,我们还要与 $0$ 再去一个 $max$,因为结果可能为负(可以想一想,为什么)

http://advntravel.com/zhanzidongji/42.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有