字符串虐哭空巢老人记

2019/01/23 22:21
阅读数 23

#字符串虐哭空巢老人记

BY:去不了冬令营的徐叔叔

本文共分两个部分:算法粗略介绍和模板、奇妙性质及其应用(优秀题目选讲)

算法模板

## 1.(树)哈希

怎么乱怎么来,越乱越好。

复杂度$\mathcal{O} (n)$

2.kmp

求最长border

for(int i=1;i<=l;i++)
{
  	int j=nxt[i-1];
  	while(j&&s[i]!=s[j+1]) j=nxt[j];
  	nxt[i]=j+(s[i]==s[j+1];
}

复杂度$\mathcal{O} (n)$

3.Manacher

求以某点为中心的最长回文

for(int i=1;i<=l;i++) s[++l]='#',s[++l]=t[i];s[++l]='#';
for(int i=1,C,R;i<=l;i++)//回文中心C 回文最右端点
{
	p[i]=i<=R?min(p[C*2-i],R-i):1;
  	while(s[i+p[i]]==s[i-p[i]]&&i+p[i]<=l&&i-p[i]>=1) p[i]++;
  	if(i+p[i]-1>R) R=i+p[i]-1,C=i;
  	Ans=max(Ans,p[i]-1);//最长回文子串
}

每次进入while时,必定R会右移

R和C两个单调指针,复杂度$\mathcal{O}(n)$

4.后缀数组

对一个字符串的所有后缀排序,并可以求出排名相邻的后缀的lcp

int cmp(int i,int j,int k) {return y[i]==y[j]&&y[i+k]==y[j+k];}
void Sort()
{
  	for(int i=1;i<=m;i++) t[i]=0;
  	for(int i=1;i<=l;i++) t[x[i]]++;
  	for(int i=1;i<=m;i++) t[i]+=t[i-1];
  	for(int i=l;i>=1;k--) SA[t[x[y[i]]]--]=y[i];
}
void GetSA()
{
 	for(int i=1;i<=l;i++) x[i]=s[i],y[i]=i;Sort();
  	for(int k=1,p=0;k<=l;k<<=1)
    {
    	for(int i=l-k+1;i<=l;i++) y[++p]=i;
      	for(int i=1;i<=l;i++) if(SA[i]>k) y[++p]=SA[i]-k;
      	Sort();swap(x,y);x[SA[1]]=p=1;
      	for(int i=2;i<=l;i++) x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;
      	if(p==m) return;m=p;p=0;
    }
  	for(int i=1;i<=l;i++) rk[SA[i]]=i;
  	for(int i=1,j=0;i<=l;i++)
    {
      	while(s[i+j]==s[SA[rk[i]-1]+j]) j++;
      	h[rk[i]]=j;if(j) j--;
    }
}

复杂度$\mathcal{O} (nlogn)$

5.(广义)后缀自动机

用一个DAG表示一个串中所有的子串。广义即多个串,要求BFS建SAM。

3+2+3行

//SAM
void Extend(int c)
{
  	int f=lst,p=++nod;lst=p;len[p]=len[f]+1;
  	while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
  	if(!f) {fa[p]=1;return;}
  	int x=ch[f][c],y=++nod;
  	if(len[x]==len[f]+1) {fa[p]=x;nod--;return;}
  	memcpy(ch[y],ch[x],sizeof(ch[y]));
  	len[y]=len[f]+1;fa[y]=fa[x];fa[x]=fa[p]=y;
  	while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
}

至于广义SAM为什么要加两个特判呢,我觉得我之前的博客并没有讲清楚

如果不加特判,直接$lst=1$,那么会加入无用节点,该节点有连边、有fail父亲,但是在DAG上无入度。绝大多数情况下,不加特判是没有问题的。

加了特判之后,没有无用节点(可能有但是没有连出去的边),并且在后方确定了下一个接节点的位置,能够保证对以后无影响。当在要记录串插到哪一个位置、用lct维护该位置fail树上的信息时,肯定就不能存无用位置了。

加特判是一个好习惯。没有加在BZOJ5408会WA,当然数据要精心构造才能卡掉。

//广义SAM
int Extend(int f,int c)
{
  	if(ch[f][c]&&len[ch[f][c]]==len[f]+1) return ch[f][c];//!
  	int p=++nod,ff=0;len[p]=len[f]+1;
  	while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
  	if(!f) {fa[p]=1;return p;}
  	int x=ch[f][c],y=++nod;
  	if(len[x]==len[f]+1) {fa[p]=x;nod--;return p;}
  	if(len[p]==len[f]+1) ff=1;//!
  	memcpy(ch[y],ch[x],sizeof(ch[y]));
  	len[y]=len[f]+1;fa[y]=fa[x];fa[x]=fa[p]=y;
  	while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
  	return ff?y:p;
}

复杂度$\mathcal{O} (n)$

6.回文树

用一个DAG表示一个串中所有的回文子串。

其每个点表示以其结尾的最长回文后缀

struct PAM
{
	int fail[N],ch[N][26],len[N],nod,lst;
  	void init() {fail[0]=fail[1]=nod=1;len[1]=-1;}//匹配奇偶回文的1、0点
  	void extend()
      	{
        	int p=lst;
      		while(s[i-len[p]-1]!=s[i]) p=fail[p];
      		if(ch[p][c]) {lst=ch[p][c];return;}
      		int x=++nod,k=fail[p];
      		lst=ch[p][c]=x;len[x]=len[p]+2;
      		while(s[i-len[k]-1]!=s[i]) k=fail[k];
      		fail[x]=ch[k][c];
      	}
}

回文树有个$fail$链上大于$\mathcal{\frac{l}{2}}$的回文长度等差的神奇性质

于是可以记录$anc[i]$表示等差数列的结尾,$diff[i]$表示公差

如果要累加答案的话,累加的是掐尾的答案(就是说不算$anc$)

7.后缀平衡树

用替罪羊树维护后缀排序,支持前端插入、删除。

核心思想为:$Suf_A$<$Suf_B$,则$s[A]<s[B]$或$s[A]==s[B]&&Suf_{A+1}<Suf_{B+1}$,即利用之前得到的信息避免了重复比较。

由此,用$double$类型存储后缀的排序关系,并以此为替罪羊树的关键字,可以实现两个后缀的$\mathcal{O}(1)$的比较。也正因为$double$的精度问题,对树高有要求,所以用替罪羊树。具体来说,替罪羊树的节点$i$表示第$i$个后缀(实际在操作过程中$reverse$了,节点$i$表示前缀$i$)

//BZOJ4768 wxh loves substring
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define lc t[x].ch[0]
#define rc t[x].ch[1]
using namespace std;
const int N=3e6+10;
const double Alpha=0.8;
struct goat{int siz,ch[2];double a;}t[N];
int mask,n,q,l,rt,tot,sta[N],top,ans;
char s[N],op[10],que[N];
void build(int &x,int L,int R,double l,double r)
{
	int MID=(L+R)>>1;   t[x=sta[MID]].siz=R-L+1;
	double mid=(l+r)/2; t[x].a=mid;
	if(L<MID) build(lc,L,MID-1,l,mid);
	if(R>MID) build(rc,MID+1,R,mid,r);
}
void pia(int &x) {if(!x) return;pia(lc);sta[++top]=x;pia(rc);x=0;}
void ins(int &x,int p,double l,double r,int fl)
{
	if(!x) {x=p;lc=rc=0;t[x].a=(l+r)/2;t[x].siz=1;return;}
	int fs=fl;t[x].siz++;
	if(s[p]<s[x]||(s[p]==s[x]&&t[p-1].a<t[x-1].a))
	{
		fs|=(t[lc].siz+1>=Alpha*t[x].siz);
		ins(lc,p,l,t[x].a,fs);
	}
	else
	{
		fs|=(t[rc].siz+1>=Alpha*t[x].siz);
		ins(rc,p,t[x].a,r,fs);
	}
	if(!fl&&fs) top=0,pia(x),build(x,1,top,l,r);
}
void upd(int x) {t[x].siz=t[lc].siz+1+t[rc].siz;}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(t[x].siz>t[y].siz) return rc=merge(rc,y),upd(x),x;
	else return t[y].ch[0]=merge(x,t[y].ch[0]),upd(y),y;
}
void del(int &x,int p)
{
	if(x!=p) t[x].siz--,del(t[p].a<t[x].a?lc:rc,p);
	else x=merge(lc,rc);
}
int query(int x)
{
	if(!x) return 0;int fl=0;
	for(int i=0;i<=l;i++)
		if(que[i]!=s[x-i]) {fl=que[i]>s[x-i];break;}
	return fl?t[lc].siz+1+query(rc):query(lc);
}
void readstr()
{
	scanf("%s",que);l=strlen(que);
	for(int i=0,tt=mask;i<l;i++)
		tt=(tt*131+i)%l,swap(que[i],que[tt]);
}
int main()
{
	cin>>q;scanf("%s",s+1);n=strlen(s+1);
	for(int i=1;i<=n;i++) ins(rt,i,0,1e9,0);
	while(q--)
	{
		scanf("%s",op);
		if(op[0]=='Q')
		{
			readstr();reverse(que,que+l);
			ans=-query(rt);que[l]='Z'+1;ans+=query(rt);
			printf("%d\n",ans);mask^=ans;
		}
		if(op[0]=='A')
		{
			readstr();
			for(int i=1;i<=l;i++)
				s[n+i]=que[i-1],ins(rt,n+i,0,1e9,0);
			n+=l;
		}
		if(op[0]=='D')
		{
			scanf("%d",&l);n-=l;
			for(int i=1;i<=l;i++) del(rt,n+i);
		}
	}
}

性质应用

一、KMP

1.带匹配的DP计数问题

HNOI2008 GT考试,求长度为$n$的不包含$S$的串的个数,$|S|\le 20$。把KMP的转移丢进矩阵即可求解

2.Border的长度限制问题

要求$Border\in [l,r]$才能对答案计算贡献,求贡献

一类问题如BZOJ3620 似乎在梦中见过的样子&&NOI2014 动物园作为好题选讲

3.Border是等差数列

一个位置上的所有Border的长度是log段等差数列

详见WC2016 论战捆竹竿

4.根据nxt数组构造原字符串

BZOJ4974 字符串大师:要求构造出来字符串最短

那么不选$ban$掉的字符贪心地构造就好了

5.用到Border方便计数的题

CTSC2006 歌唱王国作为好题选讲

二、Trie&AC自动机

1.带匹配的DP计数问题

把AC自动机建成Trie图后直接在AC自动机上走,边走边计数。

BJWC2011 禁忌:求一个长度为$10^9$的随机串不重叠地出现给定文本串的期望次数

解法就是把$AC$自动机上的转移弄成矩阵($f[i][j]$表示随机到长度i,走到AC自动机上$j$节点的概率),注意把文本串结尾位置的下一步应该是$AC$自动机的根,同时对答案产生概率$×1$的贡献。记录$g[i]$表示随机到长度$i$的期望出现的文本串个数。矩阵加速求解。

2.fail树

NOI2011 阿狸的打字机。巧妙地把问题转化为$fail$树上数点问题,拿线段树合并或其他什么东西随便搞搞就好了。

三、Manacher&PAM

1.Border是等差数列

以同一个位置结尾的所有回文子串的长度是log段等差数列

Codeforces932G Palindrome Partition YYB(redsun) orz

题意:把一个串$S$分成偶数段$s_1,s_2,s_3...s_k$并满足$s_1=s_k,s_2=s_{k-1},s_3=s_{k-2}....$的方案数,$|S|\le1e6$

题解:重构串为$S_1S_kS_2S_{k-1}S_3....$,则要求把$S'$划分成若干段,使得每一段都是偶回文的方案数。有一个显然的DP:$dp[i]$表示划分到$i$的方案数,然而转移要从$dp[1....i-1]$转移,判断条件是$S_{j...i}$是否是偶回文。用回文树优化这个转移,存一段等差数列的$dpsum$,就可以实现$\mathcal{O} (logn)$的单次转移

四、SA

求解两后缀的LCP(最长公共前缀)

大部分的题目都是求出$height$数组后在序列上xjb乱搞

结构

1.各个数组含义

$SA[i]$表示排名为$i$的后缀,$rk[i]$表示$i$后缀的排名,$h[i]$表示$LCP(Suf_{SA[i]},Suf_{SA[i-1]})$

通过$ST$表实现$\mathcal{O}(1)$的$LCP$查询

性质

1.本质不同子串问题

$Ans=sum-\sum height[i],sum=\frac{n(n+1)}{2}$

即为所有子串$-lcp$中的重复子串

2.品酒大会一类问题

就是在height上搞事情。

  • NOI2015 品酒大会:$height$上从大往小做,用并查集维护答案。
  • HEOI2016 字符串:$height$上二分查询存在性,用主席树维护答案。
  • 还有一类问题就是求出$height$后最值分治

五、SAM

求解两前缀的LCS(最长公共后缀)

结构

1.转移图

其转移图为一张$DAG$,每条从$1$到某节点的路径对应一个原串的子串这张$DAG$恰能对应出所有的子串

每个节点对应着若干从$1$到该节点的路径,也就是对应若干字符串。可以证明,这些字符串的长度是一个区间$[shortest,longest]$。

同时每个节点也有一个$endpos$集合,表示这个节点对应的所有子串的所有结尾位置

  • 关于$len$数组:$len[x]$表示该节点能表示的最长的子串长度。也就是$longest$。

2.Parent树

一个节点的$fail$父亲对应的串 是在自动机中能表示的 该节点对应串的最长后缀(意义同AC自动机)。

  • 关于$len$数组:$shortest_x=longest_{fa}+1$,也就是说一条$fail$链上的点能表示的子串长度也是连续的。
  • 关于$siz$数组:$siz[x]$表示该节点表示的子串在原串中的出现次数。在实际操作过程中,$siz$通常只打在一个点上,$siz$只有对$fail$树的子树求和才有意义,因为一个点代表的串出现了,其父亲代表的串一定出现了。

性质

1.SAM上的匹配问题

CTSC2012 熟悉的文章:在$S$中选取一些子段(不交),使得子段长度和$>|S|*90%$,且子段都是给定文本串的子串。求这些子段的最小长度的最大值。

$SAM$上的匹配直接像$AC$自动机那样顺着走就好了,只是失配的时候要跳$fail$。根据势能分析跳$fail$的次数不超过顺着走的次数,故复杂度还是$\mathcal{O} (n)$。

2.本质不同的子串问题

直接就是$\sum len[i]-len[fa[i]]$,或者可以统计DAG上有多少条拓扑路径。

然而有一种统计树上路径本质不同子串问题:ZJOI2015 诸神眷顾的幻想乡。 这题需要用到一个性质:**树上路径一定是某叶子节点到另一叶子节点的路径的子段。**所以这题叶子数很少,直接对每个叶子$dfs$后用$bfsTrie$建广义$SAM$即可

3.独特子串问题

USACO Standing Out from the Herd:求每个串的独特子串个数

用广义$SAM$,一个节点属于多个集合当且仅当其$fail$的子树内存在节点被多次访问。最后答案就是插入该串时每次的$lst$的$\sum x\ only\ belong\ to\ S_i$

4.Parent树与线段树合并(维护endpos)

快速查询某个子串在$[l,r]$内的出现次数:Codeforces700E Cool Slogans

5.Parent树与LCT(维护siz)

例如BZOJ5408 string作为好题选讲

这题主要在于维护$siz$数组,需要支持链加操作,所以用$LCT$维护。但是由于不能改变树的形态,所以不能使用$makeroot$函数,直接$Access(x)$然后$splay(x)$然后就可以直接删了。

6.SAM的后端删除

BZOJ5084 hashit:求支持后端删除的SAM中本质不同的子串个数。

  • 后缀平衡树模板:利用后缀排序求本质不同子串个数。
  • $set$做法:用$set$维护后缀排序。可以借用后缀平衡树的思想做到一个$log$,也可以用二哈做两个$log$
  • 正经SAM做法:串的轨迹是一棵Trie。你发现如果一个点在当前串内,那么该点到$fail$根的$fail$链所表示的字符串一定都出现了。所以说一个点出现了那么它的$fail$链就要算答案。所以就是维护所有出现的点的$fail$链的链并!(树链的并是一些点到根的路径的并,可以直接用$dfn$序$+set$维护,具体可见GXZlegend的标签

7.LCP向(周期串问题)

Hihocoder 后缀数组四·重复旋律4:求原串中可以被划分成最多段循环节的子串的循环节段数。

如果串$[l,r]$的周期是$len$,则$LCP(Suf_l,Suf_{l+len})>=r-l+1-len$。这个性质在Codeforces17E Palisection也有体现。

  • SA做法:枚举$len$,并且只枚举以$len$的倍数开头的位置。当所求串并不是以$len$的倍数的位置开头时,LCP会多出一段。通过那一段倒推出应该是开头的位置后再算一次LCP即可,复杂度$\cal O(nlogn)$。
  • SAM做法:固定LCS类问题,见下

8.LCP向(固定LCS类问题)

SAM支持求前缀的公共后缀,$reverse$一下就成$LCP$了

在SAM的$fail$树上固定一个点,则该点是子树内的某两点的LCS(可能不是最长,那就是某两点的CS好了)

对于上面那道题,就是固定LCP后使得$r-l$最小,于是用$set+$启发式合并维护$endpos$集合,复杂度$\cal O(nlog^2n)$

9.LCP向(区间Border)

BJWC2018 Border的四种求法:求区间Border,$n,q\le 10^5$

区间$Border$是区间内两个前缀的最长LCS(当然要在范围之内)。问题转化为求最大的$i$使得$l\le i <r,i-lcs(Pre_i,Pre_r)+1\le l$,即满足$l \le i < min(r,lcs(i,r)-l)$的最大的$i$。

得到一个暴力做法:暴力在每个$r​$处跳$fail​$链,线段树合并维护$endpos​$集合,在线段树里查 考虑正解:提交记录链接 对于在询问节点子树内的点,直接$endpos$线段树合并查询$[l,min(r,lcs(i,r)-l)-1]$内出现过的最大的i。 对于$lcs$是$fail$链上的点的情况,(想不到啊)$fail$树树链剖分后,把询问挂在各个$fa[top[x]]$。然后设计一个以位置为下标,$i-lcs+1$为权值的维护最小权值的线段树(因为要求的是满足$i-lcs+1\le l$的$i$),在重链自顶向下做一个前缀和(线段树合并),到达某询问的时候查询比$l$小的且在范围$[l,r-1]$内的最大的i是什么。具体来说,如果右儿子的最小值小于$l$则往右边递归,如果发现那个最小值不在范围之内,就回来往左递归。

酱紫每个询问被插入$log$次,查询每个询问耗时$log$,总复杂度$\cal O(nlog^2n)$。

六、Hash

1.二分+Hash(二哈求LCP)

BZOJ3946 无聊的游戏:区间插入前缀&区间查询LCP

用一个主席树维护各个位置的哈希值,然后二分判断就好了。懒标记是一棵主席树

七、其他

1.前后缀的转化

操作就是$\mathcal {reverse}$串,根据什么算法能维护什么去灵活变化

例如BJWC2018 词韵,化后缀为前缀后直接用$Trie$然后$DP$就可以了

2.子串和子序列

子串就是SAM,子序列就是序列自动机($nxt[i][j]$表示$i$位置后第一个$j$字符的出现位置)

例如HEOI2015 最短不公共子串(毒瘤四合一):给两个串A、B($len\le 2000$)

  • 求A的最短子串,使得不是B的子串
  • 求A的最短子串,使得不是B的子序列
  • 求A的最短子序列,使得不是B的子串
  • 求A的最短子序列,使得不是B的子序列

解决方式:

  • B建SAM,暴力枚举A的子串

  • 求B的$nxt$,暴力枚举A的子串

  • B建SAM,设$f[i][j]$表示A串到第$i$个位置,已经到了第$j$个SAM节点的最小子序列长度,转移就是

    f[i+1][ch[j][A[i+1]-'a']]=f[i][j]+1,f[i+1][j]=f[i][j]

    (都是取$min$,失配时贡献答案)

  • 求B的$nxt$,设$f[i][j]$,含义以及转移同上

3.通配符匹配问题

  • AHOI2005 病毒检测:若干串去匹配一个带通配符的文本串,其中*表示可以通配一段,?表示可以统配一个。串长$\le 1000$。正解:Trie+BFS。
  • CQOI2014 通配符匹配:题意同上,但串长$\le10^5$,通配符数量不超过$10$。正解:Hash+DP,设计$dp[i][j]$表示到第$i$个通配符之前,匹配上了模式串的第$j$位,相当于用通配符分割原串成若干段,每一段都用哈希判断是否相同。

To be continued...

PS:PDF阅读体验更佳,但是不会及时更新。有帮助的话点个推荐吧,mua~

展开阅读全文
lcp
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部