序列问题

Published: by Creative Commons Licence

  • Tags:

Hash算法

考虑有一个字符串$s=s_0s_1\ldots s_{n-1}$,要求快速判断字符串的某两个子串$[l,r]$和$[a,b]$是否完全相同。

我们可以用哈希算法来进行快速判断。

称$f_s(x)=\sum_{i=0}^{n-1}s_ix^{n-1-i}$是字符串$S$的哈希多项式。而对于某个选定的$x_0$,称$f_S(x_0)$为字符串$S$在$x_0$上的哈希值。

考虑两个字符串$a=a_0a_1\ldots a_{n-1}$和$b=b_0b_1\ldots b_{n-1}$。考虑$H(x)=f_a(x)-f_b(x)=\sum_{i=0}^{n-1}(a_i-b_i)x^{n-1-i}$。很显然当$A$和$B$相同的时候,$H(x)=0$,换言之,当两个字符串相同,无论$x_0$怎么选择,$H(x)$都为0,这代表着始终有$f_a(x_0)=f_b(x_0)$。

现在我们来估计误判率,即对于两个不同的字符串,两者有着相同的哈希值的概率。下面假设$a\neq b$。这时候我们会发现$H(x)\neq 0$,且阶数不超过$n-1$。

我们要证明误判率,首先需要聊聊如何防止精度溢出,一般的方法就是让其自然溢出(等价于模$2^{32}$),但是这样并不好,因为模合数的剩余类环不支持乘法逆运算,如果我们选择一个素数$p$,这样我们让结果模$p$,这时候由于模素数的剩余类环支持乘法逆运算(实际上就是域)。

一个定义在某个域上的非0多项式,其最多有和其阶数相同的零点。因此我们可以判断出$H$在模$p$的剩余类中最多有$n-1$个零点。因此假如我们随机选择$0$到$p-1$中的数作为$x_0$,那么可以推测出$P(H(x_0)=0)\leq \frac{n-1}{p}$。即误判率不超过$\frac{n}{p}$。

有时候由于生日悖论的缘故,导致哈希失败,有一种简单的方法解决,那就是独立选择多个可能的$x_1,\ldots,x_k$,只有当两个字符在任意$x_i$上取到相同的哈希值时才认为二者相同。由于选择是独立的,因此误判概率为$(\frac{n}{p})^k$。

我们可以用差分法来维护整个字符串的哈希值,这样查询某段区间字符串的哈希值时的时间复杂度为$O(1)$,在末尾增加或删除一个字符的时间复杂度为$O(1)$。

我们也可以用BIT或平衡树来维护哈希值,这样可以支持在前部增加和删除字符的操作,但是所有的操作的时间复杂度都会提高到$O(\log_2n)$。

要算二维数组的哈希,我们可以将每一行构建一个差分哈希,之后用滚动哈希的方式结合多行即可。

字符串的一些周期、border性质

对于字符串$s=s_0s_1\ldots s_{n-1}$,记$s(i..j)$表示字符串$s_is_{i+1}\ldots s_j$,记$pre(s,l)$表示$s(0..l-1)$,$suf(s,l)$表示$s(n-l..n-1)$。

如果存在整数$p$,满足$\forall i+p<n$,有$s_{p+i}=s_{i}$,那么称$p$是$s$的一个周期。

如果存在整数$b$,满足$pre(s,b)=suf(s,b)$,那么称$b$是$s$的一个border。

弱周期定理:若$p$和$q$都是字符串$s$的周期,且$p+q\leq |s|$,那么$gcd(p,q)$也是字符串$s$的周期

命题1:若字符串$u$、$v$满足$2|u|\geq |v|$,则$u$在$v$中的所有匹配位置形成一个等差数列。

命题2:若字符串$u$、$v$满足$2|u|\geq |v|$,且$u$在$v$中有两个以上匹配位置,则形成的等差数列的公差为$u$的最小周期$per(u)$

命题3:字符串$s$的所有border按长度排序后可以分成$O(\log_2|s|)$段,每一段都是一个等差数列

字符串的一些等口胡性质

以下内容仅经过个人简单证明,主要用于切题,实属口胡。

定义1:对于字符串$S$,如果存在某个前缀$P$,从$S$中删除前缀$P$并将$P$追加到结果后面,得到字符串$S'$,如果$S=S'$,那么称$\mid P\mid$是$S$的一个旋转周期。

比如对于$abab$,我们可以发现其拥有旋转周期$2$,因为$(ab)ab+ab=abab$。

命题1.1:字符串的旋转周期一定是字符串的周期

证明:

实际上旋转周期是字符串周期的一个子集。

命题1.2:如果$a$是字符串$S$的旋转周期,那么$\mid S\mid-a$也是$S$的一个旋转周期。

证明:

我们将$S$分解为两部分$A+B$,其中$A$的长度为$a$。那么我们发现$A+B=B+A=S$,这意味着将$B$移动到尾部得到的也是$S$,因此命题得证。

命题1.3:如果$a,b$是字符串$S$的旋转周期,那么$gcd(a,b)$也是$S$的一个旋转周期

证明:

不妨认为$a<b$,那么在旋转$a$后我们得到了相同的字符串$S$,而再旋转$b-a$一定能得到相同的字符串$S$。因此我们得出了$b-a$也是$S$的一个旋转周期。

利用辗转法可以得出$gcd(a,b)$是$S$的一个旋转周期。

命题1.4:长度为$n$的字符串$S$的最小旋转周期$p$,一个数$x$是$S$的旋转周期当且仅当$p\mid x$。

证明:

不妨设所有旋转周期的集合为$G$,求出$G$中所有数的最大公约数,就能得出最小旋转周期$p$。因此$p$一定是所有旋转周期的因子,同时$p$的任意倍数也一定是一个旋转周期。

定义2:对于回文$S$,如果存在某个前缀$P$,从$S$中删除前缀$P$并将$P$追加到结果后面,得到字符串$S'$,如果$S'$还是回文,那么称$\mid P\mid$是$S$的一个回文旋转周期。

命题2.1:回文的旋转周期一定是回文旋转周期

证明:

略。

命题2.2:如果$p$是回文的旋转周期,那么$pre(S,p)$一定是回文

证明:

略。

命题2.3:长度为$n$的回文$S$的最小旋转周期为$p$,如果$p$是奇数,那么$S$的最小回文旋转周期为$p$,否则$p$为偶数,$S$的最小回文旋转周期为$\frac{p}{2}$

证明:

口胡。暂时没有能力证明。

定义3:对于一个字符串$S$,称$k$为字符串的周期,当且仅当对于任意有意义的$i$和$i+k$,都有$S_i=S_{i+k}$。

命题3.1:如果$k$为字符串$S$的周期,当且仅当$S_i=S_{i\mod k}$。

一些回文题目

题目1:对于由$1$到$k$的数值组成的长度为$n$的序列,如果能通过旋转操作(将某个前缀移动到字符串尾部)将其变成回文,那么这样的序列称为特殊的。问总共有多少不同的特殊序列,结果对某个素数$p$取模。

我们可以通过统计所有满足条件的回文的最小回文旋转周期的和即可得到我们想要的结果。

我们可以枚举最小旋转周期$x$,计算最小旋转周期$x$对应的回文数目。我们知道以$x$作为旋转周期的回文有$k^{\lceil x/2\rceil}$个, 而最小旋转周期为$x$的回文可以通过容斥技术计算得到。时间复杂度为$O(D^2)$,其中$D$是$n$的因子数目。

现在认为最小旋转周期为$x$的回文有$c_x$个:如果$x$是偶数,那么它对结果的贡献应该为$\frac{1}{2}\cdot x\cdot c_x$。如果$x$是奇数,那么它对结果的贡献为$x\cdot c_x$。

提供一道Atcoder的题目

Z algorithm

最近做了这道题,一开始直接用哈希+二分来比较大数,这样时间复杂度为$O(n\log_2n)$,但是java死活跑不过去。之后发现可以通过LCP来快速定位不同的字符出现位置来加速比较,于是用了SAIS线性处理LCP,终于在900+ms内跑过了。

看了下正解,好像用的是Z algorithm,之前听过 但是一直没学,所以现在补一下。

Z algorithm用于在给定的序列$S[1..n]$上建立一个Z函数,其中$Z(i)$表示字符串$S[1..n]$和字符串$S[i..n]$的最长公共前缀长度。

下面我们来考虑如何实现线性时间处理Z函数。对于每个$i$,我们始终维护一个区间$[l,r]$,区间满足$r$最大,且$l\leq i\leq r$,且$S[l..r]$是$S[1..n]$的前缀。

我们始终设置$Z(1)=n$。接下来我们计算$Z(2),\ldots, Z(n)$。假设我们处理完了$i-1$后,接下来开始处理$i$。有几种情况:

  1. 如果此时$i=2$,那么我们就设置$l=i$,暴力计算$r$。
  2. 如果此时$r<i$,这说明不存在左边界小于$i$的包含$i$的区间(假如存在,那么就我们在处理$i-1$的时候就会有$r\geq i$)。因此我们重新设置$l=i$,并暴力计算$r$。
  3. 此时一定有$l\leq i\leq r$。我们记$t=i-l+1$,记录$k=r-i+1$,那么我们可以保证$Z(i)\geq min(Z(t), k)$,因为$S[i..n]$与$S[t..n]$的最长公共前缀长度为$k$。下面我们继续分两种情况讨论:
    1. 如果$Z(t)>k$,那么此时一定有$Z(i)=k$,且$l$和$r$不变。
    2. 否则$Z(t)\leq k$,我们可以保证$Z(i)\geq k$,这时候我们可以将$l$设置为$i$,$r$向右暴力扩展。

除了暴力操作部分,其余的操作时间复杂度都是$O(n)$。并且容易发现每次暴力操作都会使得$r$增大,而$r$只会在$i$增大时减少1,因此暴力最多发生$O(2n)$次。总的时间复杂度为$O(n)$

换了Z algorithm后,233ms就通过了。

题目1:给定一个长度为$n$的字符串$s$,定义$f(i)$表示字符串$s[0..i]$中有多少后缀与前缀相同,且后缀的长度不超过$\lfloor\frac{i+1}{2}\rfloor$。

会发现kmp适合用于求最大border,但是不适合求满足奇奇怪怪的border数目,而z函数非常适合统计border数,尤其是满足奇奇怪怪的border数目。

后缀树

很早以前了解到后缀树算法,但是一直不会。本来以为会后缀自动机就不需要学后缀树,但是,后缀自动机的各种定义太过复杂,已经忘光了,最近做到一道印度人出的,似乎要用到后缀自动机比较高级的功能,但是不会,但是假如是后缀树的话,由于是树状结构,因此是可以搞的,所以去学了下。

学习的资料:斯坦福大学课件stackoverflow大佬讲解

这里简单讲一下后缀树的特点。我们可以考虑将长度为$n$的某个序列的所有后缀插入到一株前缀树中,最后得到的就是后缀树。但是与前缀树不同的是,在前缀树中顶点代表一个字符,而后缀树中边代表一个字符。但是这样做可能会出现$O(n^2)$个顶点,于是我们可以将那些只有一个子结点的顶点与子顶点压缩成一个顶点,这样一条边就代表了某个连续子序列。由于每个后缀最后一定肯定是不同的顶点,因此会有$n$个顶点,之后每次合并都会使$n$个顶点中两个不连通的顶点连通,因此会合并$n-1$次,总的顶点数为$2n-1$。

上面的图引自wiki,大家看一下就好了。

至于代码是不可能有的,根本不会,我用的也是别人写的库。

一些后缀处理问题

问题1:给定一个字符串S,和$m$个查询,每个查询给定$l,r,X$,要求找出所有$S[l..r]$的所有字典序严格大于X的子串中最小的

这是cf的原题

一开始的想法是实现一个在线维护后缀的数据结构,但是好像不存在这种东西。于是就转向后缀树,希望能树上维护减少难度。

我的做法是这样的,首先建立S的后缀树,之后我们在后缀树上DFS,给每个叶子分配ID,且要求每个顶点子树中叶子的ID是连续的,这样我们就可以将每个顶点表示成一个区间,然后丢到线段树上进行维护。

之后我们将查询按$l$从大到小进行处理,当处理到某个$l$的时候,我们就将所有$ID$大于等于$l$的叶子激活。之后在后缀树上找到$X$对应的顶点,之后向上回溯,寻找S中是否有个较大的子串满足$r-query(L,R)+1>depth$,其中$query(L,R)$表示的是查询当且顶点子树下已经激活的ID最小的叶子的ID。

整个算法的运行时间是$O(26n+26M\log_2n)$,其中$M$是所有$X$的长度总和。

可以发现把问题丢到树上就非常容易解决。

一类序列消除问题

问题1:给定一个长度为$n$的序列,你允许操作每次删除序列的某个元素,或者一次性删除两个序列中相邻的不同的元素,问最少需要执行多少次操作,可以将序列变为空。

记$c_i$表示元素$i$的出现次数,很显然我们每次每种元素最多消除一个,因此执行次数的下限为$\max_{i}c_i$。同时如果没有任何一个元素出现次数超过一半,那么我们可以贪心的每次选择出现次数最多的元素和另外一个相邻的不同元素进行消除,这样我们就能每次消除两个元素,因此给出了一个$\lceil \frac{n}{2} \rceil$的方案。

结合上面的分析,最少次数应该为$\max(\lceil \frac{n}{2} \rceil, \max_{i}c_i)$。

问题2:给定一个长度为$n$的序列$a$,你允许操作每次删除一段漂亮子序列,问最少需要执行多少次操作,可以将序列变为空,并给出方案。一段序列$s$是漂亮序列,当且仅当序列中相邻元素都不相同,即对于任意$i$,有$s_i\neq s_{i+1}$。

我们这里要将问题做一个转换,我们构建另外一个序列$b$,对于每个$a$中相邻的两个相同元素,我们在$b$中就加入一个对应的元素,比如$a=112223$,其转换后变成$b=122$。这时候你会发现从$a$中删除一个漂亮序列,对应的就会从$b$中删除一个元素或者删除两个相邻元素,同理$b$中的删除一个元素或删除两个相邻元素对应于$a$中删除一个漂亮序列。换言之,就是我们现在需要做的就是在$b$中每次删除一个元素或删除两个相邻元素,并使之为空。这实际上就是问题1考察的,我们记结果为$r$,那么现在$b$删除为空了,对应的$a$只剩下一个漂亮序列,因此答案是$r+1$。

那么怎么求出方案呢,这里我们可以用一些平衡树维护每个字符的出现位置,用线段树记录删除位置,加上贪心算法和并查集,时间复杂度可以约束在$O(n\log_2n)$。

提供一道CF题目

问题3:给定一个长度为$n$的序列$a_1,\ldots,a_n$。我们每次可以执行这样的操作:选择两个序列中相邻的元素$x,y$,将两个数替换为$x+2y$。重复这个操作直到最后剩下一个数,问剩下的数最大是多大,记这个数为$f(a_1,\ldots,a_n)$。这个问题要求回答$q$次询问,每次询问给定$l,r$,要求求出$f(a_l,\ldots,a_r)$。这里$n,q\leq 10^5,|a_i|\leq 10^9$

我们先简化一下问题,如果替换后的数为$x+y$怎么解决?这个很简单,我们发现总和永远不会改变,因此维护一个前缀和就可以$O(1)$求解每个请求了。

再在原来的基础上增强一点,如果$a_i$始终非负如何。我们发现最终的数是每个数乘上一个系数之后加总得到的,第$i$个数能乘的最大的系数为$2^{i-1}$。因此我们可以不断选择尾部的两个元素进行替换,这样可以得到最大值$\sum_{i=1}^n2^{i-1}a_i$。那么对于多请求下,我们可以维护前缀和$g(k)=\sum_{i=1}^n2^{i-1}a_i$,之后区间$[l,r]$的最大值为$2^{-l}(g(r)-g(l-1))$。通过预处理,也可以$O(1)$处理每个请求。

好的,现在回到这个问题中来。我们从后往前处理。可以发现,对于第$i$个数,我们如果选择将其先与前面的数进行合并再与后面的数合并,就相当于后缀每个数不变,但是如果和前面的数进行合并后再和前面的数合并,那么就相当于让后缀每个数乘上2。如果后缀非负,那么我们自然希望它乘上2,否则希望它不变。这提供了一个贪心思路,我们不断从后向前处理,如果发现后缀是负数,则只乘2,同时将后缀和清0(因为会先合并所有前面的数在搞它),否则乘上2。

我们可以预先处理出每个下标$j$,最大的下标$i$,满足$i<j$且$g(j)-g(i-1)<0$。之后我们发现这些下标将整个序列分成若干个不相交的块,在上面搞个倍增就可以$O(\log_2n)$处理每个请求了。

最大表示法

考虑给定一个循环序列$s_0,s_1,\ldots,s_{n-1}$。这里我们定义循环字符串$S_i$,其第$j$个字符为$s_{i+j\mod n}$,长度为无限。这里存在共$n$个不同的起始位置以及对应的$n$个不同的循环字符串。

现在我们希望求解这$n$个循环串中字典序最大的那个。

一个简单的思路就是直接利用倍增+基数排序,可以做到$O(n\log_2n)$时间复杂度内求解。

但是有一种很精妙的线性算法存在,可以求解上述问题。

我们始终维护当前找到的字典序最大的循环串(实际上只需要维护起始坐标即可),之后不断尝试所有其它的起始位置。比较两个子串的方式就是暴力比较,但是这里有一个技巧,当我们通过比较发现$S_i$和$S_j$的最长公共前缀长度为$k$的时候,且$S_i$的第$k+1$个字符比$S_j$的大。这里我们可以直接断言,对于任意$0\leq t\leq k+1$,$j+t$一定不可能是最大循环串的的起始下标,因为其一定比以$i+t$作为起始坐标的循环串小。

利用这个性质以及双指针技术,我们会发现每次暴力比较的时候,每次比较都会将左右指针中的一个右移一位,而每个指针最多右移$n$次,因此暴力比较部分时间复杂度被约束在$O(n)$。而总的时间复杂度实际上也是$O(n)$。

邻位交换问题

题目1:给定一个$1,\ldots,n$的置换,要求对其排序。你可以完成若干次下述操作,每次选择一对邻近的元素,交换两个元素位置。至少需要多少次操作,才能让整个序列有序。

我们可以发现每次交换最多只会减少一对逆序对,且如果存在逆序对,一定存在一对相邻的逆序对。因此可以直接得出解,即原置换中逆序对的数目,这个可以通过BIT统计。

题目2:给定一个01序列,要求对其排序。你可以完成若干次下述操作,每次批次选择若干对邻近的$10$,将其全部替换成$01$。问至少需要多少次操作才能让整个序列有序。

这个问题和问题1不同,原因是它每次可以批量交换。但是由于是01序列,因此批量交换的规则也简单不少。

我们可以从左到右枚举$0$的位置,记第$i$个$0$前面有$p_i$个$1$,至少需要$r_i$轮操作才能将其移动到所有$1$之前。

对于序列前面的$0$,我们可以将其删除,不影响结果。可以发现对于第$i$个$0$,由于其前面有$p_i$个$1$,而每一轮操作它最多越过一个$1$,因此至少需要操作$p_i$轮,但是这里还需要分两种情况讨论,如果在抵达之前接触到了第$i-1$个$0$,由于不可能越过它,因此我们的操作次数应该至少为$r_{i-1}+1$,没有遇到,那么操作次数仅受前面$1$的数目所限制。因此第$i$个$0$抵达所有$1$前操作次数为$\max(r_{i-1}+1,p_i)$。

推荐一道题目:SRM783 CardboardBoxes。

惩罚函数与序列匹配问题

一般的序列匹配问题就是给定一个模式串$P$和一个字符串$S$,要求找到所有的$S$中与$P$相同的子串的起始坐标。这一类问题已经被KMP,哈希,自动机等算法按在地上摩擦了。

但是除了这些算法外,FFT也可以解决序列匹配问题。

我们记$m$为$S$的长度,$n$为$P$的长度。

我们先定义一个惩罚函数$C(i,j)=S(i)-P(j)$。之后对于某个给定的$S$中的起始下标,我们可以定义一个匹配函数$M(t)=\sum_{i=0}^{n-1}C(i+t,i)$。我们希望如果某个起始下标为$t$的$S$子串与$P$匹配,那么$M(t)=0$。

上面的定义确实能保证匹配的时候$M(t)=0$,但是不匹配的时候也是可能等于$0$的,比如$S=ab,P=ba$。这是因为惩罚函数的值可能是负数。因此一个好的距离函数应该满足$C(i,j)=0$当且仅当字符$S(i)$和$P(j)$可以匹配,其余时候都应该是正数。

于是乎一个简单的修改就是定义$C(i,j)=|S(i)-P(j)|$,现在的距离函数是正确的,但是却堵死了我们优化的门路。我们可以换一个定义:$C(i,j)=(S(i)-P(j))^2$,这也是一个好的惩罚函数的定义,但是它是可以通过FFT进行加速的。

考虑到

其中前两项都是前缀和,这个很好预处理。考虑最后一项$\sum_{i=0}^{n-1}S(i+t)P(i)$,它实际上是$S$与$P$的等差卷积中$x^t$的系数。我们可以利用快速傅里叶变换在$O(m\log_2m)$求解。

当然讲了这么多,甚至用上了重武器FFT,才能达到$O(m\log_2m)$的时间复杂度求所有起始位置,远不如线性时间复杂度的KMP和哈希。那我们为啥要学它呢?

因为用惩罚函数的方式,我们可以非常灵活的定义惩罚函数,从而计算所有匹配子串。

考虑下面几个例子:

例子1:给定长度为$n$的模式串$P$和一个字符串$S$,要求找到$P$在$S$中所有出现位置的起始下标。这里特殊的是$P$和$S$中可能存在通配符$?$,它可以匹配任意一个字符。比如$?ab$与$a?b$是匹配的。这里$n\leq m\leq 10^5$。

很显然这里KMP和哈希都是无法使用的。但是我们还是可以用惩罚函数的方式。

首先我们定义通配符$?$的值为$0$,且定义$C(i,j)=(S(i)-P(j))^2S(i)P(j)$。那么$C(i,j)$始终非负,且$0$仅在$S(i)$与$S(j)$可以匹配的时候取到。

下面我们来展开公式:

可以注意到三项都是等差卷积,因此我们可以都用$FFT$进行加速,时间复杂度为$O(m\log_2m)$。

LUOGU的一道题目

例子2:给定长度为$n$的模式串$P$和一个字符串$S$,要求找到$P$在$S$中所有出现位置的起始下标。这里匹配的含义略微不同,$P$实际上给定了另外两个序列$A$和$B$,$S(i)$与$P(j)$可以匹配当且仅当$S(i)$能与$A(j)$或$B(j)$中的至少一个匹配。

继续感受惩罚函数的美好吧。我们重新定义惩罚函数$C(i,j)=(S(i)-A(j))^2(S(i)-B(j))^2$。之后展开匹配函数:

上面的函数头两项是简单的前缀和,后面3项是等差卷积,因此时间复杂度为$O(m\log_2m)$。

一道CF题目

字典序最小子序列

给定长度为$n$的序列$a_1,\ldots,a_n$。很显然其长度为$k$的字典序最小的子序列$s(k)$是唯一的,记$f(k)=\sum_{i=1}s(k)_i$。要求输出$f(1),\ldots,f(n)$。

对于子序列$t$,若$t_i>t_{i+1}$,则称$i$是$t$的一个border(即一个非严格递增段的尾部)。这里特殊认为$|t|$也是一个border。

命题1:对于长度为$m$的序列$t$,其字典序最小的长度为$m-1$的子序列一定可以通过删除$t$中最左边的border来得到。

这是很显然的,删除一个非border,只会让自己的字典序增大,而删除一个border才可能减小字典序。删除最左边的border的效果是最好的(因为字符串比较是从左到右比较)。

命题2:$s(k-1)$是$s(k)$的子序列。

如果$s(k-1)$是$s(k)$的前缀,则命题显然成立。否则一定存在一个下标$i$,满足$\forall j<i(s(k-1)j=s(k)_j)$且$s(k-1)_i<s(k)_i$。考虑到$s(k)$是字典序最小的长度为$k$的子序列,因此$s(k-1)[i..k-1]$是$a$的后缀。记$l$表示$s(k)_1,\ldots,s(k){i-1}$是$a[1..l]$的子串,但不是$a[1..l-1]$的子串,则此时$s(k)_i$应该是$a[l..n-k+i]$中的最小值。之后拼接$s(k-1)[i..k-1]$。

命题3:$s(k-1)$可以通过$s(k)$删除最左边border得到。

由于$s(k-1)$是$s(k)$的最小子序列,而删除左边border可以让子序列最小。

因此具体算法如下:首先$f(n)=a$,之后我们不断从$f(i+1)$中删除最左边border得到$f(i)$。注意到最左边border的后一个字符的位置始终是递增的,因此可以枚举最左边border的后一个字符的位置即可。整体的时间复杂度为$O(n)$。

判断A是否是B的子串

要判断$A$是否是$B$的子串,我们可以使用贪心算法,记$f(i)$表示A的长度为$i$的前缀,是$B$的长度为$f(i)$的前缀的子串,且$f(i)$尽可能小。

可以发现$f$是个递增函数,此时$f(i)$等于最小的$j$,满足$j>f(i-1)$且$B_j=A_i$。因此我们我们用线性算法解决这个问题,时间复杂度为$O(|A|+|B|)$。

这里特殊提一下,如果有很多判断子串的请求,要求计算$A_1,A_2,\ldots,A_k$是否是$B$的子串。这时候我们可以预处理$B$,令$next(i,j)$表示最小的下标$t$,满足$t>i$且$B_t=j$。之后每次判断我们可以根据$next$表快速跳转,时间复杂度为$O(C|B|+\sum_{i=1}^k|A_i|)$,其中$C$是字符集大小。

本质不同的子串数目

给定一个长度为$n$的字符串$S$,字符集为$C$。要求计算字符串有多少本质不同的子串(子串是通过从原串删除若干个字符后得到的新的字符串,原字符串和长度为0的空串也认为是子串)。两个子串$A,B$本质不同,当且仅当长度不同或存在某个下标$i$,满足$A_i\neq B_i$。

如果不考虑本质不同,那么总共有$2^n$种子串。下面来考虑有多少本质不同的字符串。

我们回忆另外一个问题,给你两个字符串$A,B$,判断$A$是否是$B$的子串。这个问题我们有$O(|A|+|B|)$时间复杂度的贪心算法。即对于每个$A$的长度为$i$的前缀$A(i)$,记录最短的$B$的前缀$B(j)$,满足$A(i)$是$B(j)$的子串,这里我们记$P(i)=j$。可以发现$P(i)$是递增函数,因此我们找到$P(i-1)$后,一定有$P(i)>P(i-1)$,我们逐一扫描$B$的第$P(i-1)$个字符后面的字符即可。

可以发现上面提到的算法,对于给定的$A$其流程是固定的,但是对于不同的$A$,其流程两两不同。因此我们可以记$f(i)$表示满足最后一个字符恰好匹配$S_i$的本质不同的序列数目(很显然在这时候没有统计到的序列最后都不会和这些序列冲突),记$N(i,c)$表示$S$中第$i$个位置后字符$c$出现的首个下标,那么$f(i)$可以对$f(N(i,c))$产生贡献,其中$c\in C$。因此时间复杂度为$O(n|C|)$,空间复杂度为$O(n|C|)$。

提供一道题目:SRM750 PurpleSubsequences。

最短的非子串

给定长度为$n$的序列$A$,要求找出所有不是$A$的子串中长度最短的序列,如果有多个,找出其中字典序最小的。其中字符集$C$为所有小写英文字母。

我们知道如何判断一个字符串是否是$A$的子串,我们记$N(i,x)$,表示最小的$j$,满足$j>i$且$A_j=x$,如果不存在,就记$j$为$n+1$。记$B$为我们的答案。可以发现B[2..]不是A[N(0,B_1)+1..]的子串且是最短的,因此如果我们希望$B$尽可能短,则对应的希望$N(0,B_1)$尽可能大。

我们可以建立一副图,并从顶点$i$到顶点$N(i,c)$建立一条长度为1的有向边,有向边上写着字符$c$。那么问题就变成了计算从顶点$0$到顶点$n+1$的最短路径。在保证路径最短的前提下,我们要找出路径上字符组成的字符串字典序最小的那一条。

由于是无环图,因此可以直接DP解决掉。时间复杂度为$O(Cn)$。

提供一道题目

参考资料