序列问题

Published: by Creative Commons Licence

  • Tags:

字符串的一些周期、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\lt 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$的任意倍数也一定是一个旋转周期。

用这个性质,我们可以通过枚举$p$的因子得到$S$的最小旋转周期,时间复杂度为$O(n\log_2n)$(通过删除素因子的优化)。

命题1.5:长度为$n$的字符串$S$的最小旋转周期$p$一定满足$p|n$。

由命题1.4和长度n是$S$的一个旋转周期可以直接得出。

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

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

证明:

略。

命题2.2:对于回文$S$的最小回文选择周期$p$,一定满足$p\mid |S|$。

证明:

假设最小周期不能整除回文$s$,则记录$r=|S| \mod p$,记录$a=S(0..r-1)$,记录$b=S(r..p-1)$,则回文$S=abab\ldots aba$。

考虑到$p$是$S$的回文旋转周期,因此$abab\ldots aab$也是回文,即$ab=(ab)^T$,这里$x^T$表示将字符串$x$前后翻转。同时由于$S$是回文,可以得到$ab=(ba)^T$,总结可以得出$ab=ba$。之后我们考虑周期$r$,可以发现$baba\ldots abaa=abab\ldots aba=S$,即$r$也是$S$的回文旋转周期,这和$p$是最小回文旋转周期相悖。

命题2.3:如果$a,b$均为回文的回文旋转周期,则$gcd(a,b)$也是回文的旋转周期。

证明:

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

命题2.4:长度为$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的题目

题目2:给定一段长度为$n$的序列$a_1,\ldots,a_n$,要求计算它的子序列能形成多少不同的回文(空序列也是回文),结果模上素数$p$。其中$1\leq n\leq 2\times 10^3$,且$a$中仅包含小写字母。

这个问题可以通过区间DP+贪心来做。记$dp(l,r)$表示$a_l,a_{l+1},\ldots,a_r$能形成多少不同的回文。但是之后我们枚举最两端的字符即可。时间复杂度为$O(26n+13n^2)$。

题目3:给定一段长度为$n$的序列$a_1,\ldots,a_n$,要求计算有多少子序列是回文(空序列也是回文),结果模上素数$p$。其中$1\leq n\leq 2\times 10^3$,且$a$中仅包含小写字母。

这个问题也还是一个简单的区间DP。记$dp(l,r)$表示$a_l,a_{l+1},\ldots,a_r$中包含多少不同的回文子串。但是这里有一个问题,我们可以枚举左右是否匹配来计算某个状态,这时候$dp(l,r)=dp(l+1,r)+dp(l,r-1)+dp(l-1,r-1)(1+[a_l\equiv a_r])$。但是这里会存在一个重复统计的情况,$dp(l+1,r)$与$dp(l,r-1)$都包含了$dp(l-1,r-1)$的情况。

我们这边可以用一种非常简单的技术进行去重。我们定义$dp(l,r,k)$,其中$k=1$表示当前可以修改的是$r$,当$k=0$的时候表示当前可以修改的是$l$。则$dp(l,r,1)=dp(l,r-1,1)+dp(l,r,0)$,而$dp(l,r,0)=dp(l-1,r,0)+[a_l\equiv a_r]dp(l+1,r-1,1)$。可以发现这时候统计的是没有重复的。总的时间复杂度为$O(2n^2)$。

题目4:将一段长度为$n$的序列$a_1,\ldots,a_n$重复拼接$m$次,要求计算有多少子序列是回文(空序列也是回文),结果模上素数$p$,其中$1\leq n\leq 50$,$1\leq m\leq 10^{18}$,且$a$中仅包含小写字母。

我们可以记$dp(i,j,1)$表示$a_j,\ldots,a_n (i\times a)$中有多少回文子串,且下一个移动的是右端,而$dp(i,j,0)$表示$(i\times a)a_1,\ldots,a_j$中有多少回文子串,且下一个移动的是左端。

可以发现$dp(i,?,?)=Adp(i-1,?,?)$,即可以通过前一个状态通过线性变换得到,其中$A$的大小为$2n\times 2n$,其中$dp(0,?,?)$需要特殊计算。我们可以通过BM算法直接暴力计算前面几项,之后插出线性递推公式。通过一些多项式理论可以做到$O(8n^3+4n^2\log_2n)$,还是很快的。

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$的长度总和。

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

最大表示法

考虑给定一个循环序列$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)$。

惩罚函数与序列匹配问题

一般的序列匹配问题就是给定一个模式串$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进行加速的。

考虑到

\[\begin{aligned} M(t)&=\sum_{i=0}^{n-1}C(i+t,i)\\ =&\sum_{i=0}^{n-1}(S(i+t)^2+P(i)^2-S(i+t)P(i))\\ =&\sum_{i=0}^{n-1}S(i+t)^2+\sum_{i=0}^{n-1}P(i)^2-\sum_{i=0}^{n-1}S(i+t)P(i) \end{aligned}\]

其中前两项都是前缀和,这个很好预处理。考虑最后一项$\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)$可以匹配的时候取到。

下面我们来展开公式:

\[M(t)=\sum_{i=0}^{n-1}C(i+t,i)\\ =\sum_{i=0}^{n-1}(S(i+t)^3P(i)+S(i+t)P(i)^3-2S(i+t)^2P(i)^2)\\ =\sum_{i=0}^{n-1}S(i+t)^3P(i)+\sum_{i=0}^{n-1}S(i+t)P(i)^3-2\sum_{i=0}^{n-1}S(i+t)^2P(i)^2\]

可以注意到三项都是等差卷积,因此我们可以都用$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$。之后展开匹配函数:

\[M(t)=\sum_{i=0}^{n-1}C(i+t,i)\\ =\sum_{i=0}^{n-1}(S(i+t)-A(i))^2(S(i+t)-B(i))^2\\ =\sum_{i=0}^{n-1}(S(i+t)^2-S(i+t)(A(i)+B(i))+A(i)B(i))^2\\ =\sum_{i=0}^{n-1}S(i+t)^4+\sum_{i=0}^{n-1}A(i)^2B(i)^2\\ -2\sum_{i=0}^{n-1}S(i+t)(A(i)+B(i))A(i)B(i)\\ +\sum_{i=0}^{n-1}S(i+t)^2((A(i)+B(i))^2+2A(i)B(i))\\ -2\sum_{i=0}^{n-1}S(i+t)^3(A(i)+B(i))\]

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

一道CF题目

字典序最小子序列

对于子序列$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\lt i(s(k-1)_j=s(k)_j)$且$s(k-1)_i\lt 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可以让子序列最小。

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

首先$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)$。

提供一道题目

一些子串查询问题

题目1:给定$n$个名称,每个名称都有一个权重。之后有$q$个询问,询问分为两类,一类是改变某个名称的权重,还有一类就是提供另外一个字符串$s$,查询所有名称是这个字符串子串的名称的最大权重。这里$1\leq n,m\leq 5\times 10^5$,且输入的字符串总长度为$M$,满足$1\leq M\leq 10^6$,且每个名称不同。

提供一道问题https://codeforces.com/contest/1437/problem/G

这个问题涉及到子串查询,我们可以在名称上构建AC自动机。之后在fail树上建立LCT。之后每次查询,如果是修改,我们就行该对应名称中止符所在顶点的权重。而对于查询,我们查询遍历的所有顶点到根路径上权重最大的顶点的权重。这个过程总的时间复杂度为$O((n+M)\log_2n)$。

题目2:给定$n$个名称,每个名称都有一个权重。之后有$q$个询问,询问分为两类,一类是改变某个名称的权重,还有一类就是提供另外一个字符串$s$,查询所有名称包含这个字符串作为子串的名称的最大权重。这里$1\leq n,m\leq 10^5$,且输入的字符串总长度为$M$,满足$1\leq M\leq 10^5$,且每个名称不同。

我们这里是希望查询以输入的字符串作为子串,而不是一名称作为子串。我们知道AC自动机的子串查询是对于被查询的串而不是构建的串。因此我们离线请求,根据请求中的$s$构建AC自动机。之后对于名称$x$,我们发现其最多匹配$O(|x|\sqrt{M})$个字符串,每个顶点的fail链上最多有$\sqrt{M}$个不同的字符串(没给字符串长度不同)。因此总共的匹配关系仅有$O(M\sqrt{M})$,我们可以线性处理所有的查询,总的时间复杂度为$O(M\sqrt{M})$。

一些自动机

KMP自动机

KMP自动机实际上就是维护了模式串$P$的每个前缀串的border信息。当我们在KMP自动机上跑字符串$S$,其匹配的实际上是$P$的所有前缀集合与$S$的所有后缀集合中的交集中的最长元素。

KMP自动机可以一边构建一边匹配,并且KMP自动机不需要关心字符集的大小。

AC自动机

AC自动机实际上只是把KMP自动机扩展到了前缀树上。每个结点$x$的fail指针$y$,满足$y$是$x$的border。当我们在AC自动机上跑字符串$S$,其匹配的实际上是是$P$(注意这里的$P$可能有多个)的所有前缀集合与$S$的所有后缀集合中的交集中的最长元素。

AC自动机还有很多优异的特性。

  • AC自动机支持多模匹配,这是其它自动机都不能支持的
  • AC自动机的fail指针是树形的,这意味着可以在这上面使用一些树上算法
  • AC自动机的构建和匹配都是可以实现真$O(1)$的,而不是摊还$O(1)$。

但是AC自动机也有一些缺点,AC自动机不能边构建边匹配,即构建必须发生在匹配之前。

题目1:限定字符集为小写字母。给定总长为$m$的若干模式串。给定长度为$n$的字符串$S$,要求在$S$尾部添加最少的字符,使得$S$以某个模式串作为后缀。其中$1\leq n,m \leq 3\times 10^5$。

先为模式串构建AC自动机,之后在上面跑$S$。考虑我们每增加一个字符,只会使得匹配结点改变一次。我们可以在匹配结点之间建立边,每条边代表需要一个字符才能进行转移。之后实际上我们要找从当前结点出发,到某个终止符的最短距离,跑个Dijkstra即可,时间复杂度为$O(26n\log_2n)$。

题目2:限定字符集为小写字母。给定总长为$m$的若干坏字符串,要求统计有多少长度恰好为$n$的字符串,不包含任何坏字符串作为其连续子串。问存在多少这样的满足条件的字符串,结果对$p$取模。这里$1\leq m\leq 10^3$,$1\leq n\leq 10^4$。

利用坏字符串构建AC自动机。之后我们构建目标串。我们把AC自动机中的每个结点理解成状态,在目标串尾部增加新元素,会导致匹配最终状态的改变。我们记$dp(i,j)$表示构建长度为$i$,且匹配最终状态为$j$的方案数。时间复杂度为$O(26nm)$。

题目3:限定字符集为小写字母。给定$n$个总长为$m$的字符串,为每个字符串计算有多少给出的字符串是它的子串。其中$1\leq n\leq 10^4$,$1\leq m\leq 10^6$。

为所有字符串构建AC自动机。之后我们发现实际上我们关心树上$O(n)$个结点之间的可达性。我们可以通过tarjan算法求解可达性,时间复杂度为$O(26m)$。

还有一种更加简单的方式,我们对每个结点处理出沿着fail链上升时遇到的第一个终止符。之后我们为每个终止符创建一个大小为$n$的bitset。之后我们用每个模式串$i$作为输入进行匹配,对匹配遇到的顶点,在其最近终止符上打上$i$的标记。这样就能处理出有哪些字符串是其它字符串的子串。时间复杂度为$O(26m+n^2)$。

提供一道题目

题目4:限定字符集为小写字母。给定总长为$m$的若干模式串,以及长度为$n$的字符串$S$。要求统计每个模式串在$S$中的出现次数。其中$1\leq n, m\leq 10^6$。

首先为所有模式串构建AC自动机。之后在自动机上跑$S$,每次匹配新的字符,就将最后匹配结点的出现计数增加1。之后考虑fail树,每个结点的最终出现次数,都是以自己为根的子树中所有结点的计数之和。时间复杂度为$26(n+m)$。

后缀自动机

后缀自动机,原理实际上我也不是很懂,只是会实现而已。

后缀自动机中每个结点也有个fail指针,不过这个fail指针指向的是当前结点right集合的最小真超集。因此fail指针也是树形的。

后缀自动机可以一边构建一边匹配。

在后缀自动机上跑字符串$S$,得到的是$S$的后缀集合和模式串的$P$的所有连续子串集合的交集中的最大元素。因此可以很容易通过后缀自动机实现最长公共连续子串算法。

后缀自动机中每个结点都对应一个连续子串集合,且这些结点的连续子串集合是彼此不相交的。因此可以利用后缀自动机实时统计模式串中的本质不同连续子串的数目。

题目1:给定一个字符串$s$,初始是空串,之后有$n$个追加操作,每个操作向$s$尾部增加一个小写字母。要求计算每个操作完成后$s$有多少个不同的子串。其中$1\leq n\leq 10^6$。

后缀自动机可以实时统计不同子串数目,每个结点对应若干个长度不同的子串。因此只需要监控结点的状态即可。时间复杂度为$O(26n)$。

题目2:给定一个长度为$n$的字符串$s$,找到出现至少两次的最长子串并输出(空串也是合法的)。其中$1\leq n\leq 10^6$。

提供一道题目

首先我们在$s$上构建后缀自动机后,在原串上跑后缀自动机,同时计算每个结点的匹配次数。

之后我们只需要找到匹配次数超过$1$的长度最大的结点即可。可以在匹配后缀自动机的时候同时计算每个结点第一次匹配对应的下标,这样就能根据结点确定具体的串位置。

时间复杂度为$O(26n)$。

题目3:给定长度为$n$的字符串$s$,将$s$的所有不同非空子串排序后,找到其中第$k$大的结果并输出。其中$1\leq n\leq 10^6$,$k$是一个合法值。

提供一道题目

首先需要注意到后缀自动机的状态和状态转移是一个拓扑图,因此我们可以在上面进行记忆化搜索,定义$h(x)$表示从结点$x$开始转移的字符串数目。

之后我们从自动机的根开始递归,每次进入顶点的时候先减去$1$。

时间复杂度为$O(26n)$。

题目4:给定长度为$n$的字符串$s$,将$s$的所有非空子串排序后,找到其中第$k$大的结果并输出。其中$1\leq n\leq 10^6$,$k$是一个合法值。

提供一道题目

类似于题目3,但是这里在进入顶点的时候减去的是这个顶点对应的子串在原串中出现的次数。

时间复杂度为$O(26n)$。

题目5:给定$m$个总长为$n$的字符串$s_1,s_2,\ldots,s_m$,找到它们的最长公共子串。其中$1\leq m\leq n\leq 10^6$。

提供一道题目

首先我们找到这些串中最短的串,根据其构建后缀自动机。很显然公共子串一定是这个后缀自动机的某个结点代表的串。

之后我们将$m$个字符串分别丢到后缀自动机上跑,同时记录每个结点的最大匹配长度。很显然这样最后会导致每个结点记录$m$个长度,我们只需要保留其中最小值即可,因此这样只需要记录两个长度信息,一个是之前所有匹配的最大匹配长度的最小值,一个是当前匹配的最大匹配长度。

由于后缀自动机是根据长度不超过$\frac{n}{m}$的串构建的,因此总的时间复杂度为$O(26n)$。

参考资料