基本子串结构 学习笔记

Part 1 前言

基本子串结构是许廷强在 2023 年集训队论文《一类基础子串数据结构》中提出的一种新型字符串数据结构，可以同时处理前缀和后缀的信息，是一种很强力的字符串数据结构。

论文链接：国家集训队2023论文集

另外感谢 《一类基础子串数据结构》摘抄及注解 - crashed。

Part 2 基础定义

• 字符串 $S$：若无特殊说明，$S$ 为给定的某个字符串；

• 字符集大小：默认 $O(1)$；

• $|S|$ 和 $S_{[l,r]}$：

  • $|S|$ 为字符串 $S$ 的长度；
  • $S_{[l,r]}$ 为字符串 $S_lS_{l+1}\dots S_r$ 即字符串 $S$ 从 $S_l$ 到 $S_r$ 的子串；

• $\text{occ}_S(T)$、$\text{endpos}_S(T)$ 和 $\text{srtpos}_S(T)$：

  • $\text{occ}_S(T)$ 为字符串 $T$ 在字符串 $S$ 中的出现次数；
  • $\text{endpos}_S(T)$ 为字符串 $T$ 在 $S$ 中出现时的右端点位置的集合；
  • $\text{srtpos}_S(T)$ 为字符串 $T$ 在 $S$ 中出现时的左端点位置的集合；

  易知 $\text{occ}_S(T)=\text{endpos}_S(T)=\text{srtpos}_S(T)$。

  若无特殊说明，下标中的 $S$ 略去时表示 $S$ 为给定的字符串 $S$；

• $S\in T$：表示字符串 $S$ 是字符串 $T$ 的子串，$S\notin T$ 同理；

• $T_0$ 和 $T_1$：

  • $T_0$ 为正串的 SAM 的 parent 树；
  • $T_1$ 为反串的 SAM 的 parent 树；

  默认 parent 树上的节点等价于 SAM 中的对应节点；

Part 3 理论

3.1 拓展串

定义 3.1（拓展串）

$\forall t\in S$，定义 $\text{ext}(t)$ 为最长的 $S$ 的子串 $t'$ 满足 $t\in t'$ 且 $\text{occ}(t)=\text{occ}(t')$。

这个显然是良定义的，对于子串 $t$，只要不断往左往右添加字符即可找到 $\text{ext}(t)$。

定理 3.1

设 $t=S_{[l,r]},\text{ext}(t)=S_{[L,R]}$，则 $\forall l'\in[L,l],r'\in[r,R]$ 都有 $\text{ext}(S_{[l',r']})=S_{L,R}$。

由于子串 $t$ 找 $\text{ext}(t)$ 是往左往右不断添加字符。

3.2 等价类

定义 3.2.1（等价关系）

$\forall s\in S,t\in S$，$s$ 与 $t$ 等价当且仅当 $\text{ext(s)}=\text{ext(t)}$。

易证明该关系具有传递性、自反性、对称性。

定义 3.2.2（等价类和代表元）

$\forall s\in S$：

• 定义 $s$ 所在的等价类 $\text{E}(s)=\{t|t\in S,\text{ext}(t)=\text{ext}(s)\}$。

• 定义 $s$ 所在的等价类的代表元 $\text{R}(s)=t|t\in \text{E}(s),t=\text{ext}(t)$。

容易发现根据定理 3.1，$\forall s\in S$，$\text{R}(s)$ 存在且唯一。

定理 3.2

$t\in \text{E}(s)$ 当且仅当存在一个可空字符串 $c$ 满足以下两者之一：

• $s$ 和 $t$ 每次在 $S$ 中出现都是以 $tcs$ 的形式出现；
• $s$ 和 $t$ 每次在 $S$ 中出现都是以 $sct$ 的形式出现；

根据定理 3.1 易得。

3.3 引入二维平面

将 $S$ 的 $\frac{n(n+1)}{2}$ 个子串放在二维平面上，$(i,j)$ 即第 $i$ 行第 $j$ 列的点表示 $S_{[i,j]}$。

若无特殊说明，$(i,j)$ 等价于 $S_{[i,j]}$。

定理 3.3（阶梯）

每个等价类中的字符串对应的坐标最小的点在二维平面中构成了一个的右、上边界与坐标轴平行，左、下边界呈阶梯状的图形。

注意：一个等价类构成的阶梯状图形可能会重复出现很多次。

根据定理 3.1 易得。

直观感受一下，这里以 $S=abaab$ 为例：

相同颜色的串在同一个等价类中，这里一共有三个等价类。

定义 3.3（周长）

定义一个等价类 $g$ 的周长 $\text{len}(g)$ 为 $g$ 对应的阶梯状图形的宽度加上长度。

推论 3.3.1（凸性）

• 对于任意两行 $(a,*),(b,*)$，存在某个 $i$ 满足：
  • $\forall j\ge i$，$(a,j)$ 与 $(b,j)$ 在同一个等价类中；
  • $\forall j<i$，$(a,j)$ 与 $(b,j)$ 在同一个等价类中；
• 对于任意两列 $(*,a),(*,b)$，存在某个 $i$ 满足：
  • $\forall j\le i$，$(j,a)$ 与 $(j,b)$ 在同一个等价类中；
  • $\forall j>i$，$(j,a)$ 与 $(j,b)$ 在同一个等价类中；

即不存在这样的情况：

证明

由于 $T$ 和 $aT$ 在同一个等价类中，所以 $\text{endpos}(T)=\text{endpos}(aT)$。所以 $T$ 每次都是以 $aT$ 的形式出现的，那么 $Tb$ 每次肯定都是以 $aTb$ 的形式出现的，根据定理 3.2，$aTb$ 一定和 $Tb$ 在一个等价类中。

推论 3.3.2

$\forall t\in S$，$\text{occ}(t)$ 等于 $\text{E}(t)$ 对应的阶梯型出现的次数。

3.4 与 SAM 的关系

和 SAM 联系起来。

3.4.1 与节点以及 parent 树中的边的关系

定理 3.4.1.1（与节点的关系）

对于某个等价类对应的阶梯形，每一列对应 $T_0$ 中的一个节点，每一行对应 $T_1$ 中的一个节点。

证明

单看一行，所有字符串都是最长的那个的前缀，所以这些字符串等价当且仅当它们的 $\text{srtpos}$ 相等。

单看一列，所有字符串都是最长的那个的后缀，所以这些字符串等价当且仅当它们的 $\text{endpos}$ 相等。

定理 3.4.1.2（与边的关系）

• 对于二维平面中的第 $u$ 列，若 $(u,i)$ 和 $(u,i+1)$ 不在同一个等价类中则 $(u,i+1)$ 对应的 $T_0$ 中的节点是 $(u,i)$ 对应的 $T_0$ 中的节点的儿子；

• 对于二维平面中的第 $u$ 行，若 $(i,u)$ 和 $(i+1,u)$ 不在同一个等价类中则 $(i+1,u)$ 对应的 $T_1$ 中的节点是 $(i,u)$ 对应的 $T_1$ 中的节点的儿子；

反过来：

• 在 $T_0$ 上往父亲走相当于在平面上往上走到相邻的等价类；
• 在 $T_1$ 上往父亲走相当于在平面上往右走到相邻的等价类；

直观一点：（$T_1$ 上的连边在平面上的体现）

挺显然的，根据定理 3.4.1.1 立得。

推论 3.4.1（总周长线性）

对于所有等价类 $g$，$\text{len}(g)$ 的和是 $O(|S|)$ 级别的。

注意：同一个等价类对应的阶梯状图形只算一次。

证明

$\text{len}(g)$ 的和相当于满足属于不同等价类的相邻点的对数，根据定理 3.4.1.2，这样的一对点对应着 $T_0$ 或 $T_1$ 中的一条边，由于 $T_0$ 和 $T_1$ 中的边的条数都是 $O(|S|)$ 的，所以这样的点对也是 $O(|S|)$ 的。

定理 3.4.1.3（同等价类同构）

对于在同一个等价类中的同一棵 parent 树上的节点 $u,v$，它们的子树同构。

即把它们的子树看作无标号有根树后节点一一对应，且对应的两个点满足：包含的串的个数，包含的串的 $\text{occ}$ 相同，它们在二维平面上的位置差（两横/竖条的横纵距离）和 $u,v$ 在二维平面上的位置差相同。

证明

等价于对应的两个点在同一个等价类中。

根据定理 3.4.1.2，$u$ 和 $v$ 的子树中的点一定在 $u$ 和 $v$ 对应的横/竖条的上/右边，而根据推论 3.3.1，同一行/列且在同一个的两个点同时往上/右走后还在同一个等价类中。

3.4.2 再见，SAM 中的边

考虑正串 SAM 中的一条边，体现在二维平面上就是往右走，而反串 SAM 中的一条边体现在二维平面上就是往上走。

定理 3.4.2

对于 SAM 中的一条边，它连接的两个节点对应的横条/竖列在同一个等价类当且仅当它们中字符串的 $\text{endpos}$ 集合大小相同，且这样的边构成若干条链。

该定理根据定理 3.4.1.1 以及 SAM 的性质易得。

根据定理 3.4.2 和定理 3.4.1.2，容易发现正串 SAM 中的一条连接不同两个等价类的边等价于 $T_1$ 中的一条边，反串 SAM 中的一条连接不同等价类的边等价于 $T_0$ 中的一条边。

而若把一个等价类看作一个点，去掉自环，只保留每个等价类代表元的出边，那么 SAM 中的边就和另一棵 parent 树中的边一一对应了！

Part 4 实践

4.1 构建

先想清楚需要什么：

• 每个等价类的阶梯状结构（底边长、每个竖条的长度）；
• 每个等价类的代表元的第一次出现的左右端点；
• 不同等价类之间的连边：
  • 只保留每个等价类代表元的出边；
  • 横向边的和纵向边的分开；
  • 边上标注上 SAM 中对应边的字符所在的可能的最小的位置（方便定位等价类的相对位置）；

根据定理 3.4.2，把正串 SAM 中满足连接的两个节点的 $\text{endpos}$ 集合大小相同的边抽出来，不妨把这些边叫做关键边。

找到这些关键边构成的若干条链，每条链对应了一个等价类：

链的长度（点数）就是等价类底边的长度，链中每个点对应等价类中的一竖条，点中字符串的个数就是对应竖条的长度。

链尾的点中最长的字符串就是这个等价类的代表元，第一次出现的右端点可以通过在 parent 树上做子树 min 得到，第一次出现的左端点可以通过第一次出现的右端点得出。

对于不同等价类之间的边，只需要通过哈希表找到代表元在正反串 SAM 中对应的节点 $A$ 和 $B$（$A$ 是正串 SAM 上的），$A$ 的所有出边即为代表元横向的出边，$B$ 的则为代表元纵向的出边。

每条出边的字符所在的可能的最小的位置就是出边指向的节点的 $\text{endpos}$ 集合中的最小值，可以通过在 parent 树上做子树 min 得到。

梳理一下流程：

1. 建出正反 SAM，通过在 parent 树上做子树 min 得到每个节点的 $\text{endpos}$ 集合中的最小值；
2. 在正 SAM 中找到满足连接的两个节点的 $\text{endpos}$ 集合大小相同的边构成的若干条链；
3. 遍历一次所有链，对于每条链：
   1. 给这条链代表的等价类分配一个新的点 $id$，把链上节点都标记上 $id$；
   2. 得出链代表的等价类的宽度（链的长度）；
   3. 遍历一次链，得出链代表的等价类每一列的长度；
   4. 找到链尾节点 $T$ 中最长的字符串第一次出现的位置 $S_{[l,r]}$，在哈希表把 $(l,r)$ 标记为 $id$；
4. 再遍历一次所有链，对于每条链：
   1. 找到链代表的节点 $A$；
   2. 遍历链尾节点 $T$ 的所有出边 $u$：
      1. 找到 $u$ 连向的点的 $\text{endpos}$ 集合中的最小值 $x$；
      2. 找到 $u$ 连向的点的标记 $B$；
      3. 从 $A$ 向 $B$ 连一条权值为 $x$ 的横向边；
5. 在反 SAM 中找到满足连接的两个节点的 $\text{endpos}$ 集合大小相同的边构成的若干条链；
6. 遍历一次所有链，对于每条链：
   1. 找到链尾节点 $T$ 中最长的字符串第一次出现的位置 $S_{[l,r]}$，找到哈希表中 $(l,r)$ 的标记 $id$（这条链代表的节点）；
   2. 把链上节点都标记上 $id$；
7. 再遍历一次所有链，对于每条链：
   1. 找到链代表的节点 $A$；
   2. 遍历链尾节点 $T$ 的所有出边 $u$：
      1. 找到 $u$ 连向的点的 $\text{endpos}$ 集合中的最小值 $x$；
      2. 找到 $u$ 连向的点的标记 $B$；
      3. 从 $A$ 向 $B$ 连一条权值为 $x$ 的纵向边；

时间复杂度 $O(n)$，哈希表使用 map 实现则为 $O(n\log n)$。

看起来很复杂，但是看代码应该很好懂。

struct SBOOK
{
	int n;
	char str[S];
	int tot;
	struct node
	{
		int l,r;         // 代表元位置
		vector<int> len; // 每一列的长度
		vector<pair<int,int>> tor,tol; // 横向边，纵向边
	}a[S*2];
	int nxt[S*2],til[S*2],idx[S*2];
	bool vis[S*2];
	struct SAM
	{
		int lst;
		int cnt,len[S*2],to[S*2][V],link[S*2];
		vector<int> son[S*2];
		int siz[S*2],mnr[S*2];
		inline void init()
		{
			for(int i=0;i<=cnt;i++)
			{
				len[i]=link[i]=siz[i]=0;
				mnr[i]=1e8;
				memset(to[i],0,sizeof(to[i]));
				son[i].clear();
			}
			cnt=lst=0;
			link[0]=-1;
		}
		inline void ins(int r,int x)
		{
			int pre=++cnt;
			len[pre]=len[lst]+1;
			int p=lst;
			while(p!=-1&&to[p][x]==0) to[p][x]=pre,p=link[p];
			if(p==-1) link[pre]=0;
			else
			{
				int q=to[p][x];
				if(len[q]==len[p]+1) link[pre]=q;
				else
				{
					int cpy=++cnt;
					len[cpy]=len[p]+1;
					siz[cpy]=0,mnr[cpy]=1e8;
					memcpy(to[cpy],to[q],sizeof(to[q]));
					link[cpy]=link[q];
					link[pre]=cpy;
					while(p!=-1&&to[p][x]==q) to[p][x]=cpy,p=link[p];
					link[q]=cpy;
				}
			}
			lst=pre;
			siz[pre]=1;
			mnr[pre]=r;
		}
		inline void build(){for(int i=1;i<=cnt;i++) son[link[i]].push_back(i);}
		void dfs(int u=0)
		{
			for(int v:son[u])
			{
				dfs(v);
				siz[u]+=siz[v];
				mnr[u]=min(mnr[u],mnr[v]);
			}
		}
	}sam[2];
	struct HASH
	{
		int n;
		static const int mod=114547;
		vector<pair<pair<int,int>,int>> vec[mod];
		inline void init(int x)
		{
			n=x;
			for(int i=0;i<mod;i++) vec[i].clear();
		}
		inline void ins(pair<int,int> u,int val)
		{
			int idx=(1ll*u.first*n%mod+u.second)%mod;
			for(auto &v:vec[idx]) if(v.first==u) return v.second=val,void();
			vec[idx].push_back(make_pair(u,val));
		}
		inline int que(pair<int,int> u)
		{
			int idx=(1ll*u.first*n%mod+u.second)%mod;
			for(auto &v:vec[idx]) if(v.first==u) return v.second;
			return -1;
		}
	}mp;
	inline void build()
	{
		// 清空
		for(int i=1;i<=tot;i++) a[i].l=a[i].r=0,a[i].len.clear(),a[i].tor.clear(),a[i].tol.clear();
		tot=0;
		mp.init(n);
		// 建正反 SAM & 预处理节点 endpos 集合中最小值
		sam[0].init(),sam[1].init();
		for(int i=1;i<=n;i++) sam[0].ins(i,str[i]-'a');
		for(int i=n;i>=1;i--) sam[1].ins(i,str[i]-'a');
		sam[0].build(),sam[1].build();
		sam[0].dfs(),sam[1].dfs();
		// 正 SAM 找链
		for(int i=1;i<=sam[0].cnt;i++) nxt[i]=vis[i]=til[i]=0;
		for(int u=1;u<=sam[0].cnt;u++)
		{
			for(int i=0;i<V;i++)
			{
				int v=sam[0].to[u][i];
				if(v!=0&&sam[0].siz[u]==sam[0].siz[v])
				{
					nxt[u]=v;
					vis[v]=true;
				}
			}
		}
		// 正 SAM 第一次遍历链
		for(int u=1;u<=sam[0].cnt;u++)
		{
			if(!vis[u])
			{
				tot++;
				int x=u;
				while(1)
				{
					idx[x]=tot;
					a[tot].len.push_back(sam[0].len[x]-sam[0].len[sam[0].link[x]]);
					if(nxt[x]==0) break;
					x=nxt[x];
				}
				til[u]=x;
				a[tot].r=sam[0].mnr[x],a[tot].l=a[tot].r-sam[0].len[x]+1;
				mp.ins(make_pair(a[tot].l,a[tot].r),tot);
			}
		}
		// 正 SAM 第二次遍历链
		for(int u=1;u<=sam[0].cnt;u++)
		{
			if(!vis[u])
			{
				int x=til[u];
				for(int j=0;j<V;j++)
				{
					int y=sam[0].to[x][j];
					if(y==0) continue;
					int B=idx[y],val=sam[0].mnr[y];
					a[idx[x]].tor.push_back(make_pair(B,val));
				}
			}
		}
		// 反 SAM 找链
		for(int i=1;i<=sam[1].cnt;i++) nxt[i]=vis[i]=til[i]=0;
		for(int u=1;u<=sam[1].cnt;u++)
		{
			for(int i=0;i<V;i++)
			{
				int v=sam[1].to[u][i];
				if(v!=0&&sam[1].siz[u]==sam[1].siz[v])
				{
					nxt[u]=v;
					vis[v]=true;
				}
			}
		}
		// 反 SAM 第一次遍历链
		for(int u=1;u<=sam[1].cnt;u++)
		{
			if(!vis[u])
			{
				int x=u;
				while(1)
				{
					if(nxt[x]==0) break;
					x=nxt[x];
				}
				til[u]=x;
				int l=sam[1].mnr[x],r=l+sam[1].len[x]-1;
				int id=mp.que(make_pair(l,r));
				x=u;
				while(x!=0)
				{
					idx[x]=id;
					x=nxt[x];
				}
			}
		}
		// 反 SAM 第二次遍历链
		for(int u=1;u<=sam[1].cnt;u++)
		{
			if(!vis[u])
			{
				int x=til[u];
				for(int j=0;j<V;j++)
				{
					int y=sam[1].to[x][j];
					if(y==0) continue;
					int B=idx[y],val=sam[1].mnr[y];
					a[idx[x]].tol.push_back(make_pair(B,val));
				}
			}
		}
	}
};

4.2 例题

• CF1817F Entangled Substrings

  题解

  建出基本子串结构后，合法的 $a$ 和 $b$ 一定在同一个等价类中且满足它们在 $S$ 中第一次出现位置不交。

  由于已知代表元第一次出现的位置，所以等价类中每个字符串的第一次出现的位置都是可以求出来的，由于阶梯型本身具有单调性，所以对于每个阶梯型做一遍双指针即可。

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

  核心代码：

  __int128 ans=0;
  for(int i=1;i<=bok.tot;i++)
  {
         SBOOK::node &pre=bok.a[i];
         int m=pre.len.size();
         int lb=pre.l,rb=pre.r-m+1;
         __int128 sm=0;
         for(int j=m-1,k=m;j>=0;j--)
         {
             int pr=rb+j;
             while(k>=1&&lb+pre.len[k-1]-1>=pr) sm+=pre.len[--k];
             ans+=pre.len[j]*(sm-1ll*(pr-lb+1)*(m-k));
         }
  }
  

• 【2023NOI模拟赛35】字符串