周期与 Border 的结构
我们定义正整数 \(p\) 是串 \(S\) 的周期，当且仅当 \(p\le |S|\) 且 \(\forall i\in [1,|S|-p],S_i=S_{i+p}\)。
我们定义串 \(T\) 是串 \(S\) 的 border，当且仅当 \(T\) 是 \(S\) 的前缀且 \(T\) 是 \(S\) 的后缀，且 \(T\neq S\)。
周期与 border 的关系
正整数 \(p\) 是串 \(S\) 的周期，当且仅当 \(p\le |S|\) 且 \(S_{1\dots (|S|-p)}\) 是 \(S\) 的 border。
弱周期引理
若 \(p,q\) 是串 \(S\) 的周期，且 \(p+q\le |S|\)，那么 \(\gcd(p,q)\) 也是 \(S\) 的周期。
不妨设 \(p<q\)。
对于任意 \(q<i\le |S|\)，有 \(S_i=S_{i-q}=S_{i-q+p}\)。对于任意 \(q-p<i\le q\)，有 \(S_i=S_{i+p}=S_{i-q+p}\)。所以 \(q-p\) 也是 \(S\) 的周期，而 \((q-p)+p\le |S|\)，归纳可知 \(\gcd(p,q)\) 是 \(S\) 的周期。
周期引理
若 \(p,q\) 是串 \(S\) 的周期，且 \(p+q-\gcd(p,q)\le |S|\)，那么 \(\gcd(p,q)\) 也是 \(S\) 的周期。
证明略。
短周期结构
串 \(S\) 的所有长度不超过 \(\frac{|S|}{2}\) 的周期，都是其最短周期的倍数。
这是弱周期引理的直接推论。
Border 的等差数列结构
串 \(S\) 的所有 border（或周期）的长度形成了 \(O(\log |S|)\) 个值域不交的等差数列。
首先有一个引理：若 \(S_{1\dots q}\) 是 \(S\) 的 border，\(S_{1\dots p}\) 是 \(S_{1\dots q}\) 的 border，则 \(S_{1\dots p}\) 也是 \(S\) 的 border。
考虑 \(S\) 的所有长度 \(\ge \frac{|S|}{2}\) 的 border，根据“短周期结构”，它们形成一个等差数列。设长度 \(<\frac{|S|}{2}\) 的 border 中，最长的一个的长度为 \(l\)，那么长度在 \([\frac{l}{2},l]\) 中的所有 border 构成一个等差数列。以此类推，总共会形成 \(O(\log |S|)\) 个等差数列。
P3426 [POI2005] SZA-Template
给定一个字符串 \(S\)，找到一个长度最小的字符串 \(T\) 使得 \(T\) 在 \(S\) 中的所有匹配区间覆盖了整个 \([1,|S|]\cap \mathbb{Z}\)。
首先，\(T\) 一定是 \(S\) 的 border。从短到长考虑 \(S\) 的所有 border \(W\)，并维护 \(W\) 在 \(S\) 中的所有匹配位置 \(p_1<p_2<\dots<p_k\)。假如 \(\forall 1\le i<k,p_{i+1}-p_i\le |W|\)，那么 \(W\) 就是答案。
\(S_{i\dots (i+|W|-1)}=W\) 当且仅当 \(\mathrm{border}_{i+|W|-1}\ge |W|\)。所以匹配位置就是 \(\mathrm{border}\ge |W|\) 的位置，用链表维护即可。时间复杂度 \(O(n)\)。
P4156 [WC2016] 论战捆竹竿
后缀自动机
定义与性质
对于一个字符串 \(S\)，设其字符集为 \(\Sigma\)，则 \(S\) 的 SAM 就是一个最小的接受所有 \(S\) 的后缀的自动机。设 SAM 的源点 \(t_0=0\)，那么从 \(t_0\) 开始的路径与 \(S\) 的子串一一对应。
对于 \(S\) 的非空子串 \(T\)，设 \(\operatorname{endpos}(T)\) 为 \(T\) 在 \(S\) 中的所有出现位置的右端点的集合。若干个不同的 \(T\) 的 \(\operatorname{endpos}\) 可能是相同的，我们根据 \(\operatorname{endpos}\) 将 \(S\) 的所有子串分成若干个 \(\operatorname{endpos}\) 等价类，SAM 中的一个不是 \(t_0\) 的节点就代表了一个 \(\operatorname{endpos}\) 等价类，而 \(t_0\) 代表的是 \(\varnothing\)。
性质 \(1\)：若 \(T,W(|W|<|T|)\) 是 \(S\) 的两个非空子串，那么 \(\operatorname{endpos}(T)=\operatorname{endpos}(W)\) 当且仅当 \(W\) 在 \(S\) 中的所有出现都是以 \(T\) 的后缀的形式出现的。
性质 \(2\)：若 \(T,W(|W|<|T|)\) 是 \(S\) 的两个非空子串，那么它们 \(\operatorname{endpos}\) 的关系只有两种：
\[\begin{cases} \operatorname{endpos}(T)\subseteq \operatorname{endpos}(W) & W \text{is a suffix of } T\\ \operatorname{endpos}(T)\cap \operatorname{endpos}(W)=\varnothing & \text{otherwise} \end{cases} \]
性质 \(3\)：对于一个 \(\operatorname{endpos}\) 等价类，将其中的字符串按照长度从小到大排列后，对于任意两个相邻的字符串 \(T,W\)，有：
- \(T\) 是 \(W\) 的后缀；
- \(|T|=|W|-1\)。
对于 SAM 上的一个节点 \(i\)，我们定义 \(\operatorname{len}(i)\) 为 \(i\) 代表的等价类中字符串的最长长度，而 \(\operatorname{minlen}(i)\) 为最短长度。定义后缀链接 \(\operatorname{link}(i)\) 为一个节点 \(j\) 使得 \(\operatorname{len}(j)\) 最大且 \(j\) 代表的等价类的 \(\operatorname{endpos}\) 是 \(i\) 代表的等价类的 \(\operatorname{endpos}\) 的超集，特别地 \(\operatorname{link}(t_0)=-1\)。据此，我们可以得出 \(\operatorname{len}(\operatorname{link}(u))=\operatorname{minlen}(u)-1\)。
性质 \(4\)：对于所有 \(i>0\)，将 \(i\to \operatorname{link}(i)\) 间连边，则会形成一棵以 \(t_0\) 为根的内向树，这棵树描述的包含、不交关系与 \(\operatorname{endpos}\) 描述的相同。
我们考虑 SAM 中转移边的意义。设 \(\delta(u,c)\) 为点 \(u\) 添加字符 \(c\) 得到的状态，\(\operatorname{substr}(u)\) 为点 \(u\) 表示的所有字符串的集合。若两个点 \(u,v\) 之间存在转移边 \(u\xrightarrow{c} v\)，则 \(\forall T\in \operatorname{substr}(u),T+c\in \operatorname{substr}(v)\)。
性质 \(5\)：对于节点 \(v\)，设 \(\operatorname{mintrans}(v),\operatorname{maxtrans}(v)\) 分别是满足 \(\operatorname{len}(u)+1=\operatorname{minlen}(v),\operatorname{len}(u)+1=\operatorname{len}(v)\) 且存在转移边 \(u\to v\) 的 \(u\)，易证这样的 \(u\) 存在且唯一。那么对于所有存在转移边 \(u\to v\) 的 \(u\)，它们在 link 树上形成了一条 \(\operatorname{maxtrans}(v)\leadsto \operatorname{mintrans}(v)\) 的直上直下的路径。
构建
SAM 的构建是增量构造的过程，且是在线的。设我们已完成了 \(S_{1\dots (i-1)}\) 的构建，现在要加入 \(S_i\) 这个字符，\(S_{1\dots (i-1)}\) 对应的状态是 \(last\)。
新建一个节点 \(cur\)，设 \(p=last\)，我们不断地让 \(p\gets \operatorname{link}(p)\)，并令 \(\delta(p,S_i)=cur\)，直到 \(p=-1\) 或存在 \(\delta(p,S_i)\)。分类讨论：
- 若 \(p=-1\)：令 \(\operatorname{link}(cur)\gets t_0\)；
- 否则，设 \(\delta(p,S_i)=q\)，若 \(\operatorname{len}(p)+1=\operatorname{len}(q)\)，直接令 \(\operatorname{link}(cur)\gets q\) 即可。
- 否则，\(\operatorname{len}(p)+1<\operatorname{len}(q)\)。我们将 \(q\) 拆成两个状态 \(cl,q\)，并令 \(\operatorname{len}(cl)=\operatorname{len}(p)+1\)。对于任意字符 \(c\)，都令 \(\delta(cl,c)\gets \delta(q,c)\)。令 \(\operatorname{link}(cl)\gets \operatorname{link}(q),\operatorname{len}(q)\gets\operatorname{len}(cl)+1,\operatorname{link}(q)\gets cl,\operatorname{link}(cur)\gets cl\)，并将所有位于 \(p\to t_0\) 的路径上的点 \(p'\) 的 \(\delta(p',S_i)\gets cl\)。
不会复杂度证明。
struct SAM{
struct Node{
int len,link,ed,nxt[26];
}st[N*2];
int siz,last;
SAM(){
st[0]={0,-1,0,{}};
memset(st[0].nxt,-1,sizeof(st[0].nxt));
siz=1,last=0;
}
int New(){
memset(st[siz].nxt,-1,sizeof(st[siz].nxt));
return siz++;
}
void Extend(int c){
c-='a';
int cur=New();
st[cur].len=st[last].len+1;
st[cur].ed=1;
int p=last;last=cur;
while(~p&&st[p].nxt[c]==-1){
st[p].nxt[c]=cur;
p=st[p].link;
}
if(p==-1){st[cur].link=0;return;}
int q=st[p].nxt[c];
if(st[p].len+1==st[q].len) st[cur].link=q;
else{
int cl=siz++;
st[cl]={st[p].len+1,st[q].link,0,{}};
memcpy(st[cl].nxt,st[q].nxt,sizeof(st[cl].nxt));
while(~p&&st[p].nxt[c]==q){
st[p].nxt[c]=cl;
p=st[p].link;
}
st[q].link=st[cur].link=cl;
}
}
}sam;