其他字符串算法学习笔记（持续更新）

时间：2020-09-30 16:57:47 阅读：54 评论：0 收藏：0 [点我收藏+]

关于字符串Hash和后缀自动机SAM可以转至我之前的博客，这里不再阐述。

这里主要介绍一些不怎么常用（至少不如SAM和Hash）的算法。

1.SA

~~模拟退火~~后缀数组（Suffix Array）是一种很奇妙的算法。主要原因是它可以做到在 \(O(n\log n)\) 时间内完成排序。

关于如何完成这个比较基础，具体可见洛谷日报。

而后缀排序的重点在于“字典序排序”的一些奇妙性质。所以对于一般字符串的字典序排序，以下性质也适用。

首先可以发现的是 \(\operatorname{LCP}(i,j)=\min(\operatorname{LCP}(i,k),\operatorname{LCP}(k,j)),k\in[i,j]\)。这个比较显然~~主要我也不怎么会严格证明~~。具体可以见洛谷日报的证明。

考虑有了这个我们可以干什么。考虑这样一道题：按一定方式给定一堆字符串（总长度可能很大），问其中本质不同前缀的个数。

那么显然可以发现，相邻两字符串的 \(\operatorname{LCP}\) 就是他们本质相同的前缀。换句话说，除此之外的部分都是本质不同的。

而根据那个奇怪的性质，相邻两个字符串 \((x,x+1)\) 的 \(\operatorname{LCP}\) 一定 \(\geq (i,k),k\geq i+1\) 的 \(\operatorname{LCP}\)。所以显然成立。

但是这个相邻的 \(\operatorname{LCP}\) 怎么求呢？

其实是有一个很simple的 \(O(n)\) 求法。~~什么SA-IS？完全不会。~~

具体来说，我们可以求出第 \(i\) 个位置与字典序在它前面的串的 \(\operatorname{LCP}\) \(h_i\)。可以发现有 \(h_{i}=h_{i-1}+1\)。于是乎就均摊 \(O(n)\) 了。

那么我们可以做什么了呢？求本质不同子串！每个后缀的前缀唯一对应一个子串，所以直接减就好了。

例：本质不同子串

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100010
using namespace std;
int b[N],sa[N],rk[N],a[N],id[N];
char s[N];
void SA_(int n,int m)
{
	for(int i=0;i<=m;i++) b[i]=0;
	for(int i=1;i<=n;i++) b[rk[i]]++;
	for(int i=1;i<=m;i++) b[i]+=b[i-1];
	for(int i=n;i>=1;i--) sa[b[rk[id[i]]]--]=id[i];
}
void SA(int n)
{
	int m=124;
	for(int i=1;i<=n;i++) rk[i]=s[i]-‘0‘+1,id[i]=i;
	SA_(n,m);int t=0;
	for(int p=1;p<n;m=t,t=0,p<<=1)
	{
		for(int i=1;i<=p;i++) id[++t]=n-p+i;
		for(int i=1;i<=n;i++) if(sa[i]>p) id[++t]=sa[i]-p;
		SA_(n,m); swap(id,rk); rk[sa[1]]=t=1;
		for(int i=2;i<=n;i++) rk[sa[i]]=(t+=id[sa[i-1]]!=id[sa[i]] || id[sa[i-1]+p]!=id[sa[i]+p]);
	}
}
int ht[N];
void get_ht(int n)
{
	for(int i=1,p=0;i<=n;ht[rk[i]]=p,i++)
	if(rk[i]!=1) for(p=p-!!p;sa[rk[i]-1]+p<=n && i+p<=n && s[i+p]==s[sa[rk[i]-1]+p];p++);
}
int main()
{
	int n;
	scanf("%d%s",&n,s+1);
	SA(n);
	get_ht(n);
	long long ans=1ll*n*(n+1)/2;
	for(int i=1;i<=n;i++) ans-=ht[i];
	printf("%lld\n",ans);
	return 0;
}
// 压行？怎么可能？这叫 建筑美（

看到这你或许会问：这个不是SAM也能做吗？而且SAM是 \(O(n)\) 的。

的确，绝大部分SA能做的SAM都能做，而且SAM跑得快、支持在线、还更好些（~~所以我学SA干什么~~）。

别急，这里还有一个SA的晋升版本：

2.后缀平衡树（好像不一定是这么叫的）

没想到吧，后缀平衡树居然不是后缀树变过来的（我也没想到）。

首先我们还是考虑一般情况：给定一个字符串 \(S\) 的一堆子串，每次问某个子串 \(s0\) 与其他每个串的 \(\operatorname{LCP}\) 最大是多少。动态修改子串集合。

这个可以怎么做？考虑使用平衡树套Hash。具体可以见Hash学习笔记中的一道口胡的题（里面好像还有一个强制在线）。

这个是 \(O(n\log^2 n)\) 的，虽然比较暴力已经足够优秀了。但是如果我们插入的字符串有一些规律可循，是不是有更快的做法。

【模板】后缀平衡树

题意

维护一个字符串，支持加一堆字符，删一堆字符，询问某个字符出现次数。强制在线。总字符长度 \(\leq 10^6\)。

出题人真的是丧心病狂。。。

AC自动机能过？那就强制在线。

SAM还能过？那就每次加一堆字符。

啥？两只 \(\log\) 艹过去了？那就开到 \(10^6\)。~~真·5步出题法~~。

显然我们需要一个更高妙的做法。考虑多一只 \(\log\) 的瓶颈在于每次判断字典序时必须 \(O(\log n)\) 处理。再加上判断 \(O(\log n)\) 次，所以总 \(O(\log^2 n)\)。

平衡树的 \(\log n\) 没办法优化，考虑优化判断字典序。可以发现，我们要加入的字符串 \(u\) 在加入前它的前缀一定已经出现过了，所以前缀和当前要比较的节点 \(p\) 均出现过。

可以发现，当前加入的字符串 \(u\) 除了最后一个字符之外其他都与前缀 \(u-1\) 完全一致，所以我们先暴力比较 \(u\) 与 \(p\) 的最后一个字符，如果相同意味着这个 \(u-1\) 和 \(p-1\) 的字典顺序决定了 \(u\) 与 \(p\) 的字典顺序。但是直接这样比较还是 \(O(\log n)\)。

考虑如果我们维护出了所有前缀的 \(rank\)，那么显然 \(rank\) 的相对顺序就对应最后的结果。但是我们不能直接维护rank，这样会平白多出一个 \(\log n\)。考虑我们只需要知道 \(rank\) 的相对顺序即可。考虑利用平衡树的性质，每个点取一个权值 \(v_i=\frac{L+R} 2\)，然后根据 \(v_i\) 将区间分为两段递归处理。可以发现，这样满足 \(v_{ls_u}< v_u< v_{rs_u}\)。

这样建树的时间复杂度 \(O(|S|\log |S|)\)。

考虑这题维护的东西：出现次数。

这个就很好办了。考虑差分，比如要查 \(\texttt{AB}\)，我们就查字典序在 \(\texttt{AA[}\) 和 \(\texttt{AB[}\) 之间的字符。（\(\texttt{[}\) 的字典序大于所有大写字母）。具体来说，由于后缀平衡树中不存在字符 \(\texttt{[}\) ，我们可以直接用字典序小于 \(\texttt{AB[}\) 的数量减去小于 \(\texttt{AA[}\) 的数量。

由于这里需要保证相对顺序，所以我们必须使用重量平衡树，这里可以是替罪羊树（当然好像treap也行，splay应该会被卡）。

总时间复杂度 \(O(|S|\log |S|)\)，空间复杂度 \(O(|S|)\)。

特别，这里需要支持删除。但是我们不能按照普通的替罪羊树那样打标记，因为这个点会被替换掉。

所以我们直接暴力删除，按照BST的方式找到左子树中最右端的点，然后拼接上去。由于树深是 \(O(\log n)\)，所以这样复杂度也是对的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2000010
#define db double
#define alp 0.72
#define MAXD 1e16
using namespace std;
char str[N],s[N];
db v[N];
int ch[N][2],siz[N];
int swp[N],stot,rt;
void upd(int u){siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;}
void dfs(int u)
{
	if(!u) return;
	dfs(ch[u][0]),swp[++stot]=u;dfs(ch[u][1]);
	ch[u][0]=ch[u][1]=0;
}
void build(int &u,int l,int r,db lf=0,db rf=MAXD)
{
	if(l>r) return;
	int mid=(l+r)>>1;db mf=(lf+rf)/2;
	u=swp[mid];
	v[u]=mf;
	build(ch[u][0],l,mid-1,lf,mf),build(ch[u][1],mid+1,r,mf,rf);
	upd(u);
}
void reb(int &u,db lf,db rf)
{
	if(max(siz[ch[u][0]],siz[ch[u][1]])<siz[u]*alp) return;
	stot=0;dfs(u);
	build(u,1,stot,lf,rf);
}
int cmp(int x,int y){return s[x]==s[y]?v[x-1]<v[y-1]:s[x]<s[y];}
void insert(int &u,int k,db lf=0,db rf=MAXD)
{
	if(!u){siz[u=k]=1;v[u]=(lf+rf)/2;ch[u][0]=ch[u][1]=0;return;}
	if(cmp(k,u)) insert(ch[u][0],k,lf,v[u]);
	else insert(ch[u][1],k,v[u],rf);
	upd(u),reb(u,lf,rf);
}
void erase(int &u,int k)
{
	if(u==k)
	{
		if(!ch[u][0] || !ch[u][1]){u=ch[u][0]|ch[u][1];return;}
		int p=ch[u][0],las=u;
		for(;ch[p][1];las=p,p=ch[p][1]) siz[p]--;
		if(las==u) ch[p][1]=ch[u][1];
		else ch[p][0]=ch[u][0],ch[p][1]=ch[u][1],ch[las][1]=0;
		u=p;
		upd(u);
		return;
	}
	if(cmp(k,u)) erase(ch[u][0],k);
	else erase(ch[u][1],k);
	upd(u);
}
bool cmp_s(int u){for(int i=1;str[i];i++,u=u-!!u) if(str[i]!=s[u]) return str[i]<s[u];return false;}
int answer(int u)
{
	if(!u) return 0;
	if(cmp_s(u)) return answer(ch[u][0]);
	else return answer(ch[u][1])+siz[ch[u][0]]+1;
}
void get_c(char s[],int mask)
{
	int len=strlen(s);
	for(int i=0;i<len;i++)
	{
		mask=(mask*131+i)%len;
		char t=s[i];
		s[i]=s[mask];
		s[mask]=t;
	}
}
char opt[7];
int main()
{
	int n,m,k,las=0;
	scanf("%d%s",&m,s+1);n=strlen(s+1);
	for(int i=1;i<=n;i++)
	insert(rt,i);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",opt);
		if(opt[0]==‘D‘){scanf("%d",&k);while(k --> 0) erase(rt,n),n--;continue;}
		scanf("%s",str+1);
		get_c(str+1,las);
		int l=strlen(str+1);
		if(opt[0]==‘A‘) for(int j=1;j<=l;j++) s[++n]=str[j],insert(rt,n);
		else if(opt[0]==‘Q‘)
		{
			reverse(str+1,str+l+1);
			str[l+1]=‘Z‘+1,str[l+2]=‘\0‘;
			int ans=answer(rt);
			str[l]--;
			ans-=answer(rt);
			printf("%d\n",ans);
			las^=ans;
		}
	}
	return 0;
}
//压行？不存在的。

3.Lyndon 分解

逐渐黑科技了起来。

首先定义 \(\text{Lyndon Word}\) ：所有后缀中字典序最小的。

具体来说，你需要把一个字符串分解为若干个 \(\text{Lyndon Word}\)，并且字典序最小。

这里先给出结论：

我们可以贪心处理。具体来说，我们枚举当前串左端点 \(i\)，循环串的左右端点 \([l,r]\)。我们比较 \(r+1\) 和 \(l\) 的字典序。如果 \(r+1\) 大，那么我们当前的分割还是可行的。

否则就是不可行。我们直接把 \(l\) 移回当前串的左端点即可。

复杂度 \((n)\)。

具体证明在 \(\text{Runs}\) 中。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 5000010
using namespace std;
char s[N];
int p[N],t;
int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	for(int i=1,j=1,k=2;i<=n;j=i,k=i+1)
	{
		for(;k<=n && s[j]<=s[k];k++)
		{
			if(s[j]<s[k]) j=i;
			else j++;
		}
		for(;i<=j;i+=k-j) p[++t]=i+(k-j)-1;
	}
	int ans=0;
	for(int i=1;i<=t;i++) ans^=p[i];
	printf("%d\n",ans);
	return 0;
}