具体可见 2019 年陈孙立学长的集训队论文《子串周期查询问题的相关算法及其应用》，这里只提取其中重点部分。
0. 简介
基本子串字典，通俗来说，就是应用 border 及周期的一些性质来解决问题。最经典的应用是多次查询一个子串 \(S[l…r]\) 的 border 相关信息，如最小 border、最大 border 及 border 个数，通常情况下，如果不借助基本子串字典，那么该问题最优只能通过 SAM 后缀树上树链剖分做到 \(O(n\log^2n)\)（当然对于最小 border，还有较为好写的 \(n\sqrt n\) 做法，这里不再赘述），但是借助基本子串字典，我们则可以将其优化到 \(O(n\log n)\)。
1. 一些记号
方便起见，在下文中，对于字符串 \(S\)，我们做出如下定义：
- \(S[l…r]\) 表示 \(S_l\) 到 \(S_r\) 按顺序拼接起来得到的字符串，如果 \(l>r\) 那么 \(S[l…r]=\varnothing\)。
- \(\text{pre}(S,x)\) 表示 \(S\) 长度为 \(x\) 的前缀 \(S[1…x]\)，\(\text{suf}(S,x)\) 表示 \(S\) 长度为 \(x\) 的后缀 \(S[|S|-x+1…|S|]\)。
- 定义 \(S\) 长度为 \(x\) 的前缀是 \(S\) 的 border，当且仅当 \(\text{pre}(S,x)=\text{suf}(S,x)\)。
- 定义 \(S\) 存在长度为 \(x\) 的周期（period），当且仅当 \(\forall 1\le i\le n-x,S_i=S_{i+x}\)。特别地，如果 \(x\mid |S|\)，那么 \(S\) 存在长度为 \(x\) 的整周期。
- 对于两个字符串 \(S,T(|S|\ge |T|)\)，我们定义 \(T\) 在 \(S\) 中的匹配位置为所有满足 \(S[x,x+|T|-1]=T\) 的 \(x\) 组成的集合。
2. 一些与 border 有关的引理
引理 1. 字符串 \(S\) 存在长度为 \(x\) 的周期 \(\Leftrightarrow\) \(S\) 存在长度为 \(|S|-x\) 的 border。（border 与 period 的联系）
证明：显然。两者都等价于 \(\forall 1\le i\le |S|-x,S_i=S_{i+x}\)。
引理 2. 对于字符串 \(S\)，如果其存在两个大小为 \(x,y\) 的周期，且 \(x+y\le|S|\)，那么 \(S\) 也存在大小为 \(\gcd(x,y)\) 的周期（WPL）
证明：考虑 \(S\) 存在大小为 \(x,y\) 的周期意味着什么。我们在脑海里假想一个并查集维护字符相等的关系，即，如果 \(a,b\) 在并查集同一连通块中，那么意味着我们可以已经知道了 \(S_a=S_b\)，那么如果我们知道 \(S\) 存在大小为 \(x\) 的周期，就意味着我们需要对所有 \(i+x\le |S|\)，合并 \(i\) 与 \(i+x\) 所在连通块，对于长度为 \(y\) 的周期也同理。
接下来我们证明经过这两次合并之后，\(\forall i+\gcd(x,y)\le|S|\)，\(i\) 与 \(i+\gcd(x,y)\) 在同一连通块中。我们将长度为 \(x\) 的周期视作每次可以从当前点向左或向右跳 \(x\) 步，长度为 \(y\) 的周期也同理。根据斐蜀定理，必然存在 \(a,b\) 满足 \(ax+by=\gcd(x,y)\)，其中 \(a>0\) 意味着我们从 \(i\) 走到 \(i+\gcd(x,y)\) 需要向右走 \(a\) 个 \(x\) 步，\(a<0\) 则意味着需要向左走 \(-a\) 个 \(x\) 步，与 \(b\) 相关的部分也同理。而由于 \(x+y\le n\)，每次我们都能选择向左或者向右跳之一使其不离开 \([1,n]\)，因此该定理成立。
该又被称为弱周期引理 Weak Periodicity Lemma（简称 WPL）。
该定理还有一个强化版本：将上文中的 \(|S|\) 改为 \(|S|+\gcd(x,y)\) 依然成立，证明这里略去。
引理 3. 对于满足 \(S\ge |T|,2|T|\ge |S|\) 的 \(S,T\)，\(T\) 在 \(S\) 中的匹配位置构成等差数列（等差数列）
如果 \(T\) 在 \(S\) 中的出现次数 \(\le 2\)，性质显然成立，因此我们重点考虑 \(T\) 在 \(S\) 中出现次数 \(\ge 3\) 的情况。
我们假设 \(T\) 在 \(S\) 中前两次出现的位置为 \(a,b\)，另外 \(T\) 在 \(S\) 中有两个匹配位置 \(c,d\) 满足 \(d-c>b-a\)，且 \(c,d\) 中没有别的匹配位置。
因为 \(T\) 在 \(S\) 中有两个匹配位置 \(a,b\)，那么我们可以得出 \(b-a\) 是 \(T\) 的周期。而此外，由于 \(T\) 还有两个匹配位置 \(c,d\)，同样我们可以得出 \(d-c\) 也是 \(T\) 的周期。而我们可以证明，\(b-a\mid d-c\) 必然成立，因为 \(b-a\le\dfrac{n}{2}\)，根据 WPL，设 \(t=\gcd(b-a,d-c)\)，如果 \(t\ne b-a\)，那么 \(a+t\) 也是 \(T\) 的匹配位置，这样 \(T\) 的第二次匹配位置就不是 \(b\)。而再换个角度，\(c+b-a\) 也是 \(T\) 的出现位置，道理和前面相同，这与 \(d-c>b-a\) 且 \(c,d\) 中没有别的匹配位置相矛盾，所以 \(d-c=b-a\)。
该定理中涉及到“等差数列”，由此可以引出 3 个与等差数列有关的更重要的推论：
- 推论 1：\(S\) 中长度 \(\ge\dfrac{|S|}{2}\) 的 border 形成等差数列。这等价于 \(S\) 中长度 \(\le\dfrac{|S|}{2}\) 的周期成等差数列，根据 WPL，它们都是 \(S\) 的最小周期的整数倍。
- 推论 2：\(S\) 的所有 border 形成 \(O(\log n)\) 个等差数列。具体证明就是考虑找到长度 \(\le\dfrac{|S|}{2}\) 的最大的 border \(x\)，那么显然所有长度 \(\le\dfrac{|S|}{2}\) 的 border 都是 \(\text{pre}(S,x)\) 的 border，这样每次等差数列个数加 \(1\) 都伴随着长度的减半，故等差数列个数为 \(O(\log n)\)。
- 推论 3：对于任意 \(k\)，有长度在 \([k,2k)\) 中的 border 长度成等差数列。证明与推论 2 的证明类似。
3. 求解原问题
我们考虑将 \(S[l…r]\) 的 border 分为 \(O(\log n)\) 段，第 \(i\) 段处理在 \([2^i,2^{i+1})\) 中的 border，那么根据引理 3 的推论 3，这一段中的 border 长度成等差数列，因此我们只用求出首项、公差和末项就可以求出这段区间内的 border 长度的集合。
类比 ST 表，\(S[l…r]\) 存在长度为 \(j(2^i\le j<2^{i+1})\) 的 border 当且仅当 \(S[l,l+2^i-1]=S[r-j+1,r-j+2^i]\) 且 \(S[l+j-2^i,l+j-1]=S[r-2^i+1,r]\)，注意到 \(S[l,l+2^i-1]\) 和 \(S[r-2^i+1,r]\) 均为只与 \(i\) 有关的量，因此我们考虑求出 \(S[l,l+2^i-1]\) 在 \(S[r-2^{i+1}+1,r]\) 中所有出现位置，以及 \(S[r-2^i+1,r]\) 在 \(S[l,l+2^{i+1}-1]\) 中的所有出现位置，然后平移常数位后求交即可。而根据上面的引理 3， \(S[l,l+2^i-1]\) 在 \(S[r-2^{i+1}+1,r]\) 中所有出现位置成等差数列，\(S[r-2^i+1,r]\) 在 \(S[l,l+2^{i+1}-1]\) 中的所有出现位置也成等差数列，因此这个问题等价于等差数列求交。因此我们可以直接求出两个等差数列——这部分是 trivial 的，直接倍增 SA，然后对于每个本质不同的长度是 \(2\) 的幂的字符串，开桶维护其出现位置，然后在一段区间内 lower_bound 得到其第一次出现和第二次出现的位置即可。而后面等差数列求交，朴素的实现相当于求所有存在 \(0\le x<c_1,0\le y<c_2\) 且满足 \(a_1x+b_1=a_2y+b_2\) 的 \(a_1x+b_1\)，显然根据斐蜀定理解个二元一次不定方程即可。复杂度 \(\log n\)，加上枚举 \(i\) 的复杂度，\(n\log^2n\)。
但是实际上我们不用使用 exgcd 求等差数列的交。实际上对于这个情形而言可以 \(O(1)\) 求交。具体结论是，如果两个等差数列长度均 \(\ge 3\)，那么必然有两个等差数列的公差相同，这部分显然可以 \(O(1)\)，而对于存在一者长度 \(\le 2\) 的情况，暴力即可。证明可见论文。
这样我们可以 \(O(q\log n)\) 地解决问题。
4. 代码
咕了。但是 csy 说有一份实现思路很清晰的代码：https://acm.nflsoj.com/submission/50768。
原文地址：http://www.cnblogs.com/ET2006/p/dbf.html
