字符串全家桶

AC 自动机

SA

int sa[N],rk[2*N],tmp[N],buc[N];
void Sort(int n,int w){
	int ptr=0;
	for(int i=n;i>n-w;i--) tmp[++ptr]=i;
	for(int i=1;i<=n;i++) if(sa[i]-w>0) tmp[++ptr]=sa[i]-w;
	for(int i=1;i<=n;i++) buc[i]=0;
	for(int i=1;i<=n;i++) buc[rk[i]]++;
	for(int i=1;i<=n;i++) buc[i]+=buc[i-1];
	for(int i=n;i>=1;i--) sa[buc[rk[tmp[i]]]--]=tmp[i];
}
void SA(string s){
	int n=s.length()-1;
	for(int i=1;i<=n;i++) buc[s[i]]++,tmp[s[i]]=1;
	for(int i=1;i<=256;i++) buc[i]+=buc[i-1],tmp[i]+=tmp[i-1];
	for(int i=n;i>=1;i--) sa[buc[s[i]]--]=i,rk[i]=tmp[s[i]];
	for(int w=1;w<=n;w*=2){
		Sort(n,w);
		int ptr=0;
		for(int i=1;i<=n;i++){
			if(rk[sa[i]]!=rk[sa[i-1]]||rk[sa[i]+w]!=rk[sa[i-1]+w]) ptr++;
			tmp[sa[i]]=ptr;
		}
		for(int i=1;i<=n;i++) rk[i]=tmp[i];
		if(ptr==n) break;
	}
}

exKMP

文字列が嫌い

SAM

• $\operatorname{endpos}$ 相同的 $T$ 互为后缀，且长度恰为一个区间。
• 不同的 $\operatorname{endpos}$ 要么互相包含，要么无交。
• 所有的 $\operatorname{endpos}$ 的包含关系构成一棵树。
• 对于一个子串，不断删掉它的最前一个字符，$\operatorname{endpos}$ 在树上会不断跳父亲直到根。

• $\operatorname{len}(p)$ 表示对于所有 $\operatorname{endpos}(T)$ 恰为 $\operatorname{endpos}(p)$ 的 $T$ 中，最长的长度。
• $\operatorname{link}(p)$ 表示所有 $\operatorname{endpos}(q)\supset\operatorname{endpos}(p)$ 的 $q$ 中，$|\operatorname{endpos}(q)|$ 最小的那个。即 $\operatorname{endpos}$ 构成的树上的父亲。

1. $S'$ 必到达一个全新的节点，故直接新建节点 $p$ 表示 $S'$ 到达的节点，$\operatorname{len}(S')\gets\operatorname{len}(lst)+1$。
2. 若 $\delta(lst,c)$ 不存在，则 $lst$ 上的所有子串都没有后接过 $c$，直接将 $\delta(lst,c)$ 定为 $p$ 即可。然后处理 $S$ 的其它后缀后接 $c$ 的情况。具体地，直接让 $lst'\gets\operatorname{link}(lst)$，然后重复此步骤即可。
3. 现在我们不需要建新边了，而是用剩下的东西更新 $\operatorname{link}(p)$。设现在 $lst$ 为 $t$，$\delta(t,c)$ 为 $q$，分讨：
   1. $t$ 不存在。之前都没有拼上一个 $c$ 的情况，直接 $\operatorname{link}(p)\gets root$ 即可。
   2. $t$ 存在，且 $\operatorname{len}(t)+1=\operatorname{len}(q)$。此时，$q$ 上的子串恰好就是 $t$ 上的所有子串拼上一个 $c$，直接用 $q$ 更新，$\operatorname{link}(p)\gets q$ 即可。
   3. $t$ 存在，且 $\operatorname{len}(t)+1<\operatorname{len}(q)$。此时 $q$ 维护的子串中有一些过于长，并不是 $S'$ 的后缀。我们需要分裂出去一些。 设 $q'$ 为分裂出去的节点。它应该分走长度 $q$ 中长度较小的部分。即，$\operatorname{len}(q')\gets \operatorname{len}(t)+1$，$\operatorname{link}(q')\gets \operatorname{link}(q)$，然后 $\operatorname{link}(q)\gets q'$。这样便分出来了恰好是 $S'$ 的后缀的部分，直接让 $\operatorname{link}(p)\gets q'$ 即可。 原先的一些连边也需要修改。$\delta(t,c),\delta(\operatorname{link}(t),c),\delta(\operatorname{link}^2(t),c),\dotsc$ 均需要改为 $q'$。
4. 最后 $lst\gets p$ 即可。