NOI2018 你的名字

你的名字

Solution

由于水平有限,笔者对于后缀自动机的应用知之甚少。

这道题作为一道经典的后缀自动机题目,对于诸如笔者的后缀自动机初学者对于后缀自动机的认识有很大帮助。

首先考虑68分做法。

先对ssam,对于t的每一个前缀,我们找到其最长的后缀使得这个后缀是s的字串,记其的长度为mx_i。这个可以通过直接把ts的后缀自动机上匹配一遍完成。

然后对tsam,对于tsam中的每一个节点,我们找到其任意出现的一个位置,假设是[l,r],于是我们只用考虑mx_r[l,r]的影响即可,也就是把[1,mx_r-1][l,r]求一个交。

然后我们发现100分的做法,只需要考虑如何求t的所有前缀对于给定区间的mx。不难想到,只需要在ts的后缀自动机上匹配考虑“只有匹配不到才跳到fa[x]”时,同时考虑如果匹配之后到的节点的right集合中没有包含在所给区间内的右端点时也跳到fa[x]即可。

查询后缀自动机上一个节点的right集合在一个区间内有没有元素可以通过线段树合并或者主席树完成。

复杂度\mathcal{O}((|s|+|t|)log_{|s|})

发表评论

电子邮件地址不会被公开。 必填项已用*标注