字符串

发表于 分类于 Waline：

KMP

Example1(zr23省选第一轮集训day5b)

必须提一下的是,能用KMP的前提是可以比较两个字符串是否相等,不一定是比较两个字母相等.只要能比较两个字符串是否相等,并且已知\(A = B\)能快速判断是否有\(A + a = B + b\),那么就可以使用KMP.并不要求\(A = B\)并且\(a = b\)才有\(A + a = B + b\).

因此,我们取\(p\)的置换\(q\),然后找到所有和\(q\)的大小关系一样的区间即可,要证明这是个等价关系,然后就可以上KMP了.

Example2(NOI2014 动物园)

自然的想法是先求border数组,然后每次暴力跳border直到当前前后缀不重叠.根据border的定义显然是对的.但这样复杂度不对.

另一个想法是我们能不能在做KMP的时候,直接判掉当前长度是否超过,如果超过就放弃呢?也不对,因为这样往前跳也会用到这个border数组,但往前跳有可能跳的很少.

因此我们先求border,再第二遍做KMP,用另一个数组,但是往前跳的时候用border跳,其他情况正常做就行.

border理论

定理

定理1

\(s\)的某个border长度为\(k\)等价于\(| s | - k\)是\(s\)的周期.

证明显然.

定理2(周期引理)

弱周期引理:如果\(p , q\)是\(s\)的周期且\(p + q \leq | s |\),那么\(\gcd ( p , q )\)是\(s\)的周期.

考虑分开两面证明,不妨设\(p > q , r = p - q\),先证明\(\forall i > q , s_i = s_{ i + r }\),事实上\(s_i = s_{ i - q } = s_{ i - q + p } = s_{ i + r }\).再考虑证明\(i \leq | s | - p , s_i = s_{ i + r }\),事实上\(s_i = s_{ i + p } = s_{ i + p - q } = s_{ i + r }\).

由于\(p + q \leq | s |\),因此上面那个证明对所有\(i\)成立,由此得证.

强周期引理:如果\(p , q\)是\(s\)的周期且\(p + q - \gcd ( p , q ) \leq | s |\),那么\(\gcd ( p , q )\)是\(s\)的周期.

这个有一个生成函数证明.简单来说我们不妨设长度为\(p\)的那个周期的生成函数为\(P ( z )\),它是一个\(p - 1\)次的生成函数.同理定义\(Q ( z )\).不妨设\(S_p ( z ) = \frac{ P ( z ) }{ 1 - z^p }\),同理定义\(S_q ( z )\).

如果我们能说明\(S_p ( z ) = S_q ( z )\),由于这两个都是无穷项,由欧几里得算法立刻得到\(\gcd ( p , q )\)是其周期.考虑:

\[ \begin{aligned} & S_p ( z ) - S_q ( z ) \\ = & \frac{ P ( z ) }{ 1 - z^p } - \frac{ Q ( z ) }{ 1 - z^q } \\ = & \frac{ 1 - z^g }{ ( 1 - z^p ) ( 1 - z^q ) } ( \frac{ 1 - z^q }{ 1 - z^g } P ( z ) - \frac{ 1 - z^p }{ 1 - z^g } Q ( z ) ) \end{aligned} \]

此时注意到括号里面的那个东西的次数有限,设其为\(H ( z )\),不难发现\(H ( z )\)的次数是\(p + q - g - 1\).若\(H ( z ) \ne 0\),又因为\(\frac{ 1 - z^g }{ ( 1 - z^p ) ( 1 - z^q ) }\)的常数项不为\(0\),因此\(\exists 0 \leq k \leq p + q - g - 1 , [ z^k ] ( S_p ( z ) - S_q ( z ) ) \ne 0\),但根据假设,\(\forall 0 \leq k \leq n - 1 \leq p + q - g - 1\),应该有\([ z^k ] ( S_p ( z ) - S_q ( z ) ) = 0\),因此\(H ( z ) = 0\),因此\(S_p ( z ) = S_q ( z )\).

定理3

若\(S\)是\(T\)的前缀,且\(T\)有周期\(a\),\(S\)有整周期\(b\),\(b | a , | S | \geq a\),则\(T\)有周期\(b\).证明显然.

定理4

若\(2 | S | \geq | T |\),则\(S\)在\(T\)中的匹配位置必为等差序列.

证明考虑WPL就行.

定理5

\(S\)的长度大于等于\(\frac{ n }{ 2 }\)的border长度构成一个等差序列.

不妨设最长的border长度为\(n - p\),还有一个border长度是\(n - q\),\(q > p\),那么必有长度为\(n - \gcd ( p , q )\)的border.注意到\(n - p\)是最长的border,则\(\gcd ( p , q ) \geq p\),\(p | q\).

定理6

一个串的所有border按照长度排序后,可以被划分成\(O ( \log n )\)个等差序列.

首先,将该串的长度\(\geq \frac{ n }{ 2 }\)的border拿出作为一个等差序列.考虑这些中长度最小的\(T\).

再考虑最小循环节\(d\),如果\(d \leq \frac{ n }{ 4 }\),那么不断减小一定有\(| T | \leq \frac{ 3 }{ 4 } n\).反之则最长border本身就\(\leq \frac{ 3 }{ 4 } n\),于是剩下的border都是\(T\)的border.这样就证明了\(O ( \log n )\),事实上更紧凑的界是\(\lceil \log_2 | S | \rceil\),不会证.

Example

Example1([POI2011]OKR-Periodicity)

注意到一个事实:如果这个字符串存在长度为\(k\)的周期,等价于存在长度为\(len - k\)的border,证明是显然的.

考虑从小周期开始向大周期确定,首先可以用KMP求出所有前缀的最大border,然后就可以得到整个字符串的所有border.换句话说,我们实际上是在一步一步确定整个字符串的若干前缀的最大border.

考虑border理论,设\(q\)为最小周期,如果\(2 q < n\),也就是原串能写成\(tt \cdots t '\)的形式.我们不妨先求\(tt '\)对应的答案,然后在前面拼\(t\).根据\(\leq \frac{ n }{ 2 }\)的border构成等差序列的结论,这样显然是正确的.

如果\(2 q \geq n\),此时必定有\(s = tat\),其中\(t\)是border.考虑递归求解\(t\),然后就只需要找到一个\(a\)满足条件,最小的\(a\)是全\(0\),能放的话肯定放,不然我们就放一个\(0 \cdots 01\).

为什么这样一定是对的呢?我们考虑什么时候全\(0\)不合法:

  1. 新增一个长度\(l\)的border,\(l \leq | t | + | a |\):考虑\(l\)的最后一段是一段全\(0\),也就必然意味着\(t\)的最后一段是全\(0\),这么不断推下去就可以说明整个序列都是全\(0\),此时放上\(0 \cdots 01\)必定合法.

  2. 新增一个长度\(l\)的border,\(l > | t | + | a |\):不妨设当前的\(l\)是最大的那个(最小的无意义,因为需要保证\(| l | > | t |\)),此时最短周期必然是\(d = 2 | t | + | a | - l\).由于\(| t | + | a |\)也是周期并且二者之和\(\leq n\),因此必然有\(d | ( | t | + | a | )\).把\(ta\)按照\(d\)长度划分.如果\(d \geq | a |\)必有该串是全\(0\)串,不然考虑此时\(d = | b | + | a |\),\(b\)是\(t\)的一段后缀.考虑此时的周期必然\(< | b | + | a |\),首先不可能等于,如果大于的话可以平移一格.不妨假设周期比\(| b | - | a |\)少了\(w\),那么此时必定有\(b\)的前\(w\)个字符是\(0\),但是由于\(0 \cdots 01\)后面第一个\(b\)也往前平移了\(w\)格,因此它的第\(w\)个字符必定是\(1\),这就保证了\(0 \cdots 0 1\)必定合法.

SA

Example1

给定一个长度为\(n\)的字符串,要从中从左往右选出若干段不相交的子串,使得选出的这些串中,每个串都是上一个串的严格子串.求最多能选出多少段.\(n \leq 5 \times 10^5\).

不难发现一定有一组答案每段的长度是\(k , k - 1 , \cdots , 2 , 1\),我们不妨把串反过来,这样就是\(1 , 2 , \cdots , k - 1 , k\).这样就可以设计一个简单的dp是\(f_{ i , j }\)表示以\(i\)结尾,\(i\)这段长度为\(j\)是否可行,发现单调性后把dp状态扔进值里,\(f_i\)表示以\(i\)结尾的最大长度是多少,这样用SA做lcp就可以实现\(O ( n^2 )\).仔细观察转移过程,我们可以二分答案,然后用主席树+SA判断答案是否可行.复杂度\(O ( n \log^2 n )\).

那么怎么优化呢?我们考虑类似height的证明:\(f_i \leq f_{ i - 1 } + 1\),原因很简单,如果\(f_i > f_{ i - 1 } + 1\),那么我们把\(f_i\)那个序列的末尾字符全部删掉,自然得到了一个以\(i - 1\)结尾,长度为\(f_i - 1 > f_{ i - 1 }\)的串,于是就可以类似height那样去掉二分,很厉害.

ACAM

用于对于每个文本串的前缀,求出它以哪些模式串为后缀.

Example1(uoj772企鹅游戏)

考虑一个暴力:建出\(s\)的AC自动机,然后我们记录fail树结构,然后把\(t\)放上去跑,每次暴力向上跳fail树上的匹配节点,这样的复杂度就是\(O ( \sum 匹 配 节 点 个 数 )\).

但是这个复杂度是正确的.

为啥呢?首先对于任意节点,它在fail树上的祖先中匹配节点个数不可能超过\(O ( \sqrt{ L } )\)个,这是个自然根号,因此复杂度至少是\(O ( L \sqrt{ L } )\).

但还没完,考虑所有长度小于等于\(B\)的模式串,他们会被匹配\(O ( B | t | )\)次.对于所有长度大于\(B\)的模式串,考虑只有长度大于\(B\)的文本串会匹配到他们,于是复杂度\(O ( \frac{ L^2 }{ B^2 } )\),\(B = L^{ \frac{ 1 }{ 3 } }\)得到\(O ( L^{ \frac{ 4 }{ 3 } } )\).

Example2(loj3396 novel)

offline.

PAM

引理

  1. 本质不同回文串最多只有\(n\)个.

证明:考虑类似manacher,每次将\(S \rightarrow S + c\),新产生的回文串一定是\(S + c\)的最长回文后缀.

算法

回文自动机由转移边和fail树构成,经过一条转移边的影响是在前后均添加一个该字符,一个状态在fail树上指向它的最长回文border.

我们记录两个根:长度为\(- 1\)的奇根和长度为\(0\)的偶根,偶根的失配指针指向奇根.

增量构造,每次加入个新字符,然后在fail树上跳祖先直到\(s_i = s_{ i - len - 1 }\).

继续跳这个节点,直到又遇到一个位置,那这个位置就是当前节点的fail指针所指向的点.这个操作是\(O ( n )\)的,因为这个fail指针只有一个永远不会访问,另外的都会访问至少一次,在访问的时候就会均摊掉求的时候往上跳的复杂度,因为深度直接减去这玩意了.

SAM

  1. \(endpos ( T )\)表示子串\(T\)在\(S\)中出现位置的末尾集合,特别地,我们设\(endpos ( \emptyset ) = \{ 1 , \cdots , | S | - 1 , | S | \}\).

  2. 若两个不同的子串的\(endpos\)相等,则称它们为一个\(endpos\)等价类.

下面开始证明引理:

引理

  1. 字符串\(s\)的两个非空子串\(u\)和\(w\)的\(endpos\)相同(假设\(| u | \leq | w |\)),当且仅当字符串\(u\)在\(s\)中的每次出现,都是以\(w\)后缀的形式存在.

  2. 字符串\(s\)的两个非空子串\(u\)和\(w\)的\(endpos\)集合的交为空(假设\(| u | \leq | w |\)),当且仅当字符串\(u\)不是\(w\)的后缀.

  3. 字符串\(s\)的两个非空子串\(u\)和\(w\)的\(endpos\)集合的交为\(endpos ( w )\)(假设\(| u | \leq | w |\)),当且仅当字符串\(u\)是\(w\)的后缀.

证明都是显然的.

  1. 对于一个\(endpos\)等价类中的子串\(u\),要么\(u\)是这个等价类中最短的子串,要么存在一个子串\(w\)且\(| w | + 1 = | u |\),\(w\)是\(u\)的后缀

由前面的引理,容易证明.

  1. 对于一个\(endpos\)等价类中最短的子串\(w\),不妨设\(v\)是\(w\)去掉最前面的元素后得到的子串,那么\(v\)在另一个\(endpos\)等价类中,我们将\(endpos ( w ) \rightarrow endpos ( v )\),记\(link ( w ) = v\)或\(fa ( w ) = v\),这就是后缀链接link,这些关系构成树.

首先除了\(\emptyset\),每个\(w\)的出度都是\(1\),而我们发现所有的子串都会以\(\emptyset\)作为祖先,这就证明了连通性.

  1. \(endpos\)等价类的数量有\(O ( n )\)个.

考虑后缀链接树,显然一个点的\(endpos\)集合包含它的所有儿子的\(endpos\)集合的并,并且它所有儿子的\(endpos\)集合两两无交,这等价于一个合并的过程.

约定

  1. 记\(longest ( v )\)为\(v\)这个\(endpos\)等价类中最长的一个字符串,记\(len ( v )\)为它的长度.类似地定义\(shortest ( v )\)和\(minlen ( v )\),不难发现\(minlen ( v ) = len ( fa ( v ) ) + 1\).每个节点的子串数量也就是\(len ( v ) - len ( fa ( v ) )\).

  2. 记\(siz ( v )\)为\(v\)这个\(endpos\)等价类的\(endpos\)集合的大小.

算法

先来捋一下整个过程:整个SAM分为两部分:

第一部分:后缀链接树(parent tree).

它的信息由下文中的fa记录.对于每一个节点:它对应一个endpos等价类,因此它拥有一个父亲节点,也就是后缀链接link指向的节点.同时它拥有一个len,表示这个endpos等价类中最长的子串的长度.

第二部分:trie图.

它的信息由下文中的son记录,表示一个endpos(设为x)通过一条trie边走到另一个endpos(设为y),不难发现x中的所有endpos+1所形成的集合包含y.我们注意这一点后,会发现只要从\(\emptyset\)所代表的节点不断地走trie边,最后走到的节点的对应长度的子串就是我们想要的子串.这也意味着我们要保证对应长度的子串一定在走到节点的子串集合中.另外有个结论是trie图的边数是\(O ( n )\)的.这必然要求走trie走到的那个节点的\(len\)的长度的区间包含了这个节点的\(len\)的长度的区间\(+ 1\).

也就是说,走trie边的过程是不断在字符串后面添加字符的过程,而走link的过程是不断在字符串前面删去字符串的过程(当然,反向link自然是不断在字符串前面加上另一个字符串集合的过程).

下面给出构造代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
struct SAM{
int fa;
int son[27];
int len,siz;
}tr[MAXN<<1|1];
int cntp=1,las=1;
int End[MAXN];
inline void add_c(int c,int i){
int x=++cntp;
End[i]=x;tr[x].siz=1;//新建一个endpos={i}
//End[i]存的是前缀[1,i]的结束位置,由于我们当前正在插入i,自然是x.
int prex=las;
las=cntp;
//las存储的是当前的终止节点,其实也就是End[i],我们每次要找到上一次的终止节点,根据它来操作.
tr[x].len=tr[prex].len+1;
for(;prex&&tr[prex].son[c]==0;prex=tr[prex].fa)tr[prex].son[c]=x;
//考虑当前的串:[1,i-1]+'c',如果前面存在一个endpos集合包含[j,i-1](这个集合可能是空子串所在的集合)并且它存在一条'c'边,那么就存在这么一个子串[j,i-1]+'c',它的endpos应该是{i}这个集合的祖先.
//如果在判断[j,i-1]的时候,发现[j,i-1]+'c'在原串中不存在,那么我们就直接连过来.可以发现在这个跳跃的过程中就是不断探索当前x的shortest的过程.
if(!prex){
//说明一直到最后都没有找到字母c,这也意味着c在前面根本没出现过,于是endpos={i}的等价类是[1,i],[2,i],...,[i,i],所以父亲设为1.
tr[x].fa=1;
return ;
}
int y=tr[prex].son[c];
//考虑这里的prex到底是什么意义,它意味着我们找到了一个最长的[j,i-1]的子串所在的endpos集合,并且[j,i-1]+'c'这个子串在原串存在,这也意味着[j,i-1]+'c'这个子串所在的endpos集合必然真包含{i},而这个子串的长度是tr[prex].len+1.
if(tr[y].len==tr[prex].len+1){
//如果y这个节点的长度恰好也是tr[prex].len+1,那么必然意味着[j,i]这个子串完全就在y这里,而[j-1,i]这些子串不在y这里,但被y表示的endpos集合包含.
tr[x].fa=y;
}
else {
//反之,这里y这个节点的endpos集合就可以分成两部分了:第一部分的endpos集合在加入[j,i]这个子串后不变:因为它们的长度都大于tr[prex].len+1,它们必然不可能存在一个endpos是i.而第二部分,其实也只包含一个子串:就是长度等于tr[prex].len+1的子串,它的endpos集合必然是第一部分的endpos集合并上{i},根据我们上面所发现的parent tree的本质是合并endpos集合的性质,它应该是第一部分以及{i}的父亲(也就是这两部分合并的结果),我们把第二部分拿出来单独建点.
int fay=++cntp;
tr[fay]=tr[y];
tr[fay].len=tr[prex].len+1;
tr[y].fa=tr[x].fa=fay;
for(;prex&&tr[prex].son[c]==y;prex=tr[prex].fa)tr[prex].son[c]=fay;
//注意单独建点后,原本指向y的trie边要改向.这是为什么呢?考虑当前这条边是什么意义:它必然指向一个endpos集合要包含{i}的点,因为这样才能保证trie图的性质.此时指向y的点就不能是包含{i-1}的点了.
}
return ;
}
int que[MAXN<<1],l,r;
int ind[MAXn<<1];
inline void work_siz(){//通过一次拓扑排序处理出siz
l=1,r=0;
for(int i=1;i<=cnt;++i){
++ind[tr[i].fa];
}
for(int i=1;i<=cnt;++i){
if(ind[i]==0)que[++r]=i;
}
while(l<=r){
int x=que[l];++l;
tr[tr[x].fa].siz+=tr[x].siz;
--ind[tr[x].fa];
if(ind[tr[x].fa]==0)que[++r]=tr[x].fa;
}
return ;
}

其实还是省掉了很多说明:比如这里的复杂度证明以及边数证明,但是我们咕了吧.

应用

检查字符串是否出现

从根开始跳trie边就行.

不同子串个数

显然是\(\sum len_i - len_{ fa_i }\).

例题

Example1

给出一个长度为\(n\)的小写字母串,你需要计算有多少对非空字符串\(( A , B )\)满足:

  1. \(AB\)是原串的子串.

  2. 每次\(A\)在原串中作为子串出现后,要么紧跟着出现一个子串\(B\),要么\(A\)后面放不下一个子串\(B\).

两个字符串被认为是不同的当且仅当他们在某个位置上字母不同,\(| S | \leq 2 \times 10^5\).

首先,我们考虑确定\(( AB , A )\)这个二元组,对反串建立SAM,我们自然有:

  1. \(AB\)的endpos集合是\(A\)的endpos集合的后缀.

  2. \(A\)的endpos集合中存在的最大的不存在于\(AB\)的endpos集合的endpos的大小小于\(| AB |\).

看到这里你可能有疑问:为啥要建立反串.因为不建立反串的话\(( AB , B )\)的endpos可能根本没啥区别,这个很难处理\(A\).SAM最强大的武器还是在于它能快速处理endpos.

那么接下来我们要在SAM上判断这两件事,我们需要一些更方便判断的条件.首先一个自然的发现是,\(A\)的最大的endpos必然也是\(AB\)的最大的endpos,我们进行一个类似重链剖分的操作:将每个点的重儿子设为它所有儿子中最大的endpos最大的那个.不难发现此时的\(A\)与\(AB\)必然在同一条重链上,且\(A\)是\(AB\)的祖先.不过显然这并不能保证一定是后缀,我们开始补条件,直到补到它充要:另一个显然的条件是,设\(mx_v\)表示节点\(v\)的轻儿子中最大的endpos最大是多少,那么\(A\)与\(AB\)间的所有\(mx\)的最大值就是\(A\)的endpos集合中存在的最大的不存在于\(AB\)的endpos集合的endpos的大小,它需要小于\(| AB |\).进一步发现这个数字必然需要小于\(AB\)的endpos的集合中最小的那个(不然就不是后缀),这被包含于小于\(| AB |\)这个条件.

接下来就拆重链,写单调栈就行.