@qq290637843
2021-07-07T05:11:35.000000Z
字数 5351
阅读 1117
子串周期查询
二、周期、边界、前后缀的一些性质
下文用表示的最小周期。
发现1：字符串以为周期，当且仅当有长为的边界。
根据发现1可知只需要有的所有边界的长度，就有了所有周期。下文将的所有边界的长度构成的集合记为，将的所有边界的长度构成的集合记为。
事实1（周期引理）：若一个字符串长为且具有周期和，且，那么该字符串也具有周期。
下文将中大于的数构成的集合记为。
引理1：如果，那么为一等差数列。
证明：根据发现1，中任何数都对应着小于的周期。根据周期引理可知，任何小于的周期都是的倍数，于是这些周期构成一个等差数列，于是这些周期所对应的边界长度构成一个等差数列。
下文用表示的所有基础子串构成的集合，所谓的基础子串是指的长度为的整次方数的子串。
如果既是的前缀，又是的后缀，那么将称为的前后缀。现在假设，且的某个前后缀满足，那么称是的大前后缀。对于的任何两个等长基础子串，用表示的大前后缀的长度构成的集合。
引理2：设且。那么构成一个等差数列。
证明：设。设是的长为的后缀。那么。于是根据引理1直接得证。
三、算法的主体
下文中用表示最大的小于等于的的整次方数。
记为，记为。
算法如下：
求的所有周期构成的集合
第一步：设
第二步：对每个：
第三步：
第四步：返回。
其中表示的长为的整次方的前缀和后缀构成的字符串对构成的序列。
引理3：对于的所有周期的查询，可以依靠两部分完成：第一部分是次对的查询，其中且；第二部分是一次对的查询，其中。
四、关于和的查询
对于以及下标，定义如下两个函数：
：且，满足以上条件的最小；
：且，满足以上条件的最大。
对于两个字符串，用表示在的所有出现位置的开头下标构成的集合。
下述事实直接由周期引理得出：
事实2：考虑两个非空字符串和，且。那么为一等差数列。如果，那么该等差数列的公差就是。
引理4：如果是的子串，且，那么的等差数列表示只需要在上进行次查询。
证明：设。首先我们进行两个查询：和。如果或者不存在，那么任务已经完成。根据事实2，是等差数列。根据和，我们知道了首项和公差。最后，查询来得出末项。
引理5：设并且。并且设以及，其中。那么：
证明：注意如果，那么当且仅当并且，见下图。
引理6：设并且。如果且，那么，也就是说，和具有相同的公差。
证明：设以及。假设。设。的大小说明和的出现位置的覆盖区域至少为。这个覆盖区域对应着的一个后缀，且该后缀具有周期和，根据周期引理，也就具有周期。这意味着具有周期，矛盾。的情况的证明相似。
发现2：如果我们已经有两个公差一致的等差数列的压缩表示（首项、末项、公差），那么求它们的交的压缩表示所需时间是的。
根据以上引理，可以设计一个求的算法：
第一步：如果，只需检查的真假；
第二步：设，且。
第三步：（根据引理4）
第四步：
如果或那么（非周期的情况）
依靠检查小的那个集合的元素求出
另一个情况，那么（周期情况，根据引理6）
求出，由于这两个数列的公差一致。
返回。
根据以上算法可知
引理7：如果。那么可以用次查询以及次其他操作完成。
引理8：对于的子串，以及，可以靠次查询完成。
证明：根据引理1的证明，中的所有数都对应着的最小周期的倍数，并且该集合非空仅当，其小于等于。
设是的长为的前缀。其在中的第一次出现是作为前缀出现。使用查出第二个出现位置。如果其不存在，说明是空集。否则，设是两个出现位置的差。
于是是的长度小于的最小周期的唯一可能性。这是因为，如果，那么将会在更早的位置出现，也就是。如果，那么的长为的前缀会有周期和，于是，根据周期引理，也将是的周期，矛盾。
现在我们需要检查是不是的周期，我们知道其是的周期。这时需要使用一次查询。设是的长为的后缀，使用一次查询，就可找到作为的子串在上一次出现的位置。如果该位置存在并且位置差距为，那么是的周期，由于和覆盖了，是的周期。否则不可能是的周期。
综上，我们解决了的查询问题。
五、的实现方式
首先，直接用后缀树或者后缀数组，然后再用一个可持久化线段树就能轻松实现查询，于是总时间复杂度会变为。后文将说明针对该问题，如何将查询优化到期望（需要的预处理时间）。
引理9：对于长为的字符串，可以建立一个大小的数据结构，使得所有针对的以及查询都能期望完成。建立该数据结构的时间。
证明：对于每一个，确定其在后缀树上对应的位置，记为（这可以借助于在后缀树上深搜完成），将其在中的出现位置分为个集合（其中一些可能是空集）。表示起点属于的那些出现位置。根据事实2，这些集合中每一个都一定是等差数列。
接着建立一个哈希表，以作为输入，且仅当真的存在才有这个数据节点。的输出是是指的压缩表示（注意，是等差数列）。由于在中的总出现次数是的，所以的总大小也是的，并且建立时间也是的。
有了以上哈希表，查询显然就是期望的了。
