NOI2018 你的名字

你的名字

Solution

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

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

首先考虑$68$分做法。

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

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

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

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

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

发表评论

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