Border理论小记

部分图源 —— 金策 : 《字符串算法选讲》,2017 看不懂的 Border 论，写不顺的 KMP。 # KMP算法 讲个笑话，当教练画了个字符串算法层级图，叫我们尽量使用“低级算法”解决问题，我发现自己不会最底层的 `KMP`…… **作用** : 对于一个字符串 $S$ ，对于每个 $i$ 求出 $S[\_,i]$ 与 $S$ 匹配的最大长度。 就是把 $S$ 的每个前缀与自身匹配，且不能无脑重合，问最长能匹配多长。 ```cpp 例 : ababb a ab ababb ababb 匹配上了 0 位 匹配上了 0 位 aba abab ababb ababb 匹配上了 1 位 匹配上了 2 位 ababb ababb 匹配上了 0 位 ``` 怎么求呢? 回忆AC自动机的内容，发现这个最短不重合可匹配前缀就是 `fail` ! （手动狗头 但是 `AC` 自动机的正确建立方法需要补 `Trie` 图，这玩意就不必如此麻烦了，直接暴力跳 `fail` ，直到有对应出边即可。 由于跳一次`fail`，匹配位数必然减少，所以复杂度是均摊正确的。 然后，我们就可以在这个自动机上匹配其他的串，得到每个前缀的匹配长度，同样暴力跳 `fail` ，复杂度也是均摊的。 可以拿来做单串匹配，给匹配串建立自动机，求出文本串每个前缀的匹配长度。 若某个位置的匹配长度为匹配串串长，则说明完整匹配了。 - [P3375 【模板】KMP字符串匹配](https://www.luogu.com.cn/problem/P3375) 这题终于不是橙色而是黄色了，感天动地! 生涯第一次 `1A` 的 `KMP` /ll ```cpp #include<algorithm> #include<cstring> #include<cstdio> #define MaxN 1000500 using namespace std; void build(char *s,int len,int *fail) { int p=0; for (int i=2;i<=len;i++){ while(p&&s[p+1]!=s[i])p=fail[p]; if (s[p+1]==s[i])p++; fail[i]=p; } } void match(char *s,char *t,int len,int *fail,int *sl) { int p=0; for (int i=1;i<=len;i++){ while(p&&s[p+1]!=t[i])p=fail[p]; if (s[p+1]==t[i])p++; sl[i]=p; } } char s[MaxN],t[MaxN]; int tp[MaxN],sl[MaxN],len1,len2; int main() { scanf("%s%s",t+1,s+1); len1=strlen(s+1);len2=strlen(t+1); build(s,len1,tp); match(s,t,len2,tp,sl); for (int i=1;i<=len2;i++) if (sl[i]==len1)printf("%d\n",i-len1+1); for (int i=1;i<=len1;i++) printf("%d ",tp[i]); return 0; } ``` - [P3193 [HNOI2008]GT考试](https://www.luogu.com.cn/problem/P3193) 设模式串为 $S$ ，文本串为 $T$。 首先设计一个朴素 $\rm DP$ ，设 $f[i][j]$ 为文本匹配了前缀 $i$ ，模板匹配了前缀 $j$ 的方案数 $(0\leq j< |S|)$。 我们只要把 $j=|S|$ 的情况剔除，就能够保证模式串不出现。 设 $g[i][j]$ 为已经匹配了长度 $i$ ，新加一个字符使得匹配长度变为 $j$ 的方案数。 则有转移 : $f[i+1][j]=\sum\limits_{k=0}^{|S|-1}f[i][k]g[k][j]$ 不难发现， $g$ 是由模板串唯一确定的。 而上述转移正是矩阵乘法，使用矩阵快速幂即可 $O(|S|^3\log n)$ 计算。 边界是 $f[0][0]=1$ ，所以答案是矩阵第 $0$ 行的和。 现在考虑如何算出 $g$。 枚举当前匹配的长度 $p$ 和即将添加的字符 $ch$。 - 多匹配了一位。匹配长度加一。$(ch=s[p+1])$ - 跳回某个前缀，发现能够匹配了。 (和 `KMP` 一样跳 $fail$) - 失配。(跳到根发现仍然无法匹配) 这部分的复杂度是 $O(|S|^2\Sigma)$ 的。 其实就是 `KMP` 自动机，所以有 $O(|S|\Sigma)$ 的做法。 [评测记录](https://www.luogu.com.cn/record/34510326) - **扩展KMP（Z函数）** 给出串 $S$ ，定义 $z[i]={\rm lcp}(S,s[i,n])$ 。 求 $z[1]...z[n]$ ，即 $S$ 的所有后缀与 $S$ 的 $\rm LCP$。 定义 $z[0]=0$ ，且然有 $z[1]=|S|$。接下来按照 $z[2]...z[|S|]$ 的顺序求解。 定义一个 $l$ 处的匹配段 $[l,r]$ 为 $\big[l,l+z[l]-1\big]$ ，维护右端点最靠后的匹配段 $[l,r]$。 在计算 $z[i]$ 时，显然有 $l<i$。若此时 $i<r$ ，则将 $z[i]$ 初始化为 $0$ 然后暴力扩展。 否则由 $s[1,r-l+1]=s[l,r]$ ，可以利用 $z[i-l+1]$ 的值。若 $z[i-l+1]<r-i+1$ 则表明 $z[i]=z[i-l+1]$。 否则，将 $z[i]$ 初始化为 $r-i+1$ ，然后暴力扩展 $z[i]$ 并更新 $[l,r]$。 不难发现，暴力匹配的过程中 $r$ 一直随之增大，所以总复杂度是 $O(n)$ 的。 求出 $z$ 函数之后，可以进一步求解匹配问题，方法类似，具体见代码 ： [P5410 【模板】扩展 KMP（Z 函数）](https://www.luogu.com.cn/problem/P5410) ```cpp #include<algorithm> #include<cstring> #include<cstdio> #define ll long long #define MaxN 20005000 using namespace std; void zkmp(char *a,int n,int *z) { z[1]=n; for (int i=2,l=0,r=0;i<=n;i++){ z[i]=(r<i) ? 0 : min(z[i-l+1],r-i+1); while(i+z[i]<=n&&a[i+z[i]]==a[z[i]+1])z[i]++; if (i+z[i]-1>r){l=i;r=i+z[i]-1;} } } void zmatch(char *a,int na,char *b,int nb,int *z,int *p) { for (int i=1,l=0,r=0;i<=na;i++){ p[i]=(r<i) ? 0 : min(z[i-l+1],r-i+1); while(i+p[i]<=na&&a[i+p[i]]==b[p[i]+1])p[i]++; if (i+p[i]-1>r){l=i;r=i+p[i]-1;} } } char a[MaxN],b[MaxN]; int z[MaxN],p[MaxN]; void calc(int *z,int n) { ll ans=0; for (int i=1;i<=n;i++) ans^=1ll*i*(z[i]+1); printf("%lld\n",ans); } int main() { scanf("%s%s",a+1,b+1); int na=strlen(a+1),nb=strlen(b+1); zkmp(b,nb,z);calc(z,nb); zmatch(a,na,b,nb,z,p);calc(p,na); return 0; } ``` # Border 的一些性质 - **Border 相关的定义&约定** 用 $|S|$ 表示 $S$ 的长度。若只有一个串， $n$ 一般指原串长度。 $\Sigma$ 指字符集。 $\color{blue}\text{定义:}$ $\rm Border$ : 字符串的某个前缀(**非原串**)，能与后缀完全匹配。 如 $S[1,m]=S[n-m+1,n]$ 则称 $S[1,m]$ 为一个 $\rm Border$。 下面会简称为 $\rm Bd$。 设 ${\rm mxBd}(S)$ 为 $S$ 的最大 $\rm Bd$ ，而 ${\rm Bd}(S)$ 为 $S$ 的 $\rm Bd$ 集合。 若对于 $p$ ,有 $S[i]=S[i+p]$ ，称 $p$ 是 $S$ 的周期。 $S[1,p]$ 是 $\rm Bd\Longleftrightarrow$ $|S|-p$ 是 $S$ 的周期  若 $p|n$ 称为整周期。 - **KMP 与 Border 的关系** 能够发现， `KMP` 的 `fail` 数组刻画的就是各个前缀的 $\rm mxBd$。 - **求出某个串的所有 Border** 当然,你也可以按照定义无脑 `Hash`，但是这里有个更加有理有据的作法。 - $\color{blue}\text{定理(1):}$ ${\rm Bd}(S)={\rm mxBd}(S)+{\rm Bd}({\rm mxBd}(S))$ 用人话说， $\rm mxBd$ 加上 $\rm mxBd$ 的 $\rm Bd$ **恰是**原串所有的 $\rm Bd$。 $\color{blue}\text{证明:}$ - 右侧 $\subseteq$ 左侧 : $\rm Bd$ 的 $\rm Bd$ 是 $\rm Bd$。 若有 $S[1,m]=S[n-m+1,n]$ 且 $S[1,m_2]=S[m-m_2+1,m]$ , 即 $S[1,m_2]$ 是 $S[1,m]$ 的 $\rm Bd$ ， $S[1,m]$ 是 $S[1,n]$ 的 $\rm Bd$。 把等式连接，则有 $S[m-m_2+1,m]=S[n-m_2+1,n]$ ，所以 $S[1,m_2]$ 是 $S[1,n]$ 的 $\rm Bd$。 如果用图来表示就很直观了 ： 原串是 $S$ ，$A$ 是 $S$ 的 $\rm Bd$ ，$B$ 是 $A$ 的 $\rm Bd$。 $\begin{aligned} &\qquad\qquad\qquad\qquad\boxed{\qquad\qquad B\qquad\qquad} \\&\qquad\qquad\boxed{\qquad\qquad\qquad A\qquad\qquad\qquad} \\&\boxed{\qquad\qquad\qquad\qquad S\qquad\qquad\qquad\qquad} \\&\boxed{\qquad\qquad\qquad A\qquad\qquad\qquad} \\&\boxed{\qquad\qquad B\qquad\qquad} \end{aligned}$ 显然 $B$ 也是 $S$ 的 $\rm Bd$。 - 左侧 $\subseteq$ 右侧 : $\rm Bd$ 是 $\rm mxBd$ 的 $\rm Bd$。 假设有 $S[1,m_2]=S[n-m_2+1,n]$ ， 且 $S[1,m]=S[n-m+1,n]$ ($m$ 代表最大的 $\rm Bd$) 即 $S[1,m],S[1,m_2]$ 均是原串的 $\rm Bd$。 把等式连接，则有 $S[m-m_2+1,m]=S[m-m_2+1,m]$ ，所以 $S[1,m_2]$ 是 $S[1,m]$ 的 $\rm Bd$。 图还是那张图。 而 $\rm Bd$ 必然是原串的前缀，我们先用 `KMP` 求出所有前缀的 $\rm mxBd$ ，然后从 $n$ 不断跳 `fail` 即可得到原串的所有 `Border` 。 $S$ 的所有 $\rm Bd$ 长度 : $\{fail[n],fail[fail[n]]...\}$。 - [P3435 [POI2006]OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435) 由于 $\rm Bd$ 与周期对应，题意就是求每个前缀的最小非空 $\rm Bd$。 可以暴力跳 $fail$ 查询所有 $\rm Bd$ ，发现小非空 $\rm Bd$ 即为 $fail$ 树祖先最浅非根点，加个记忆化即可。 [评测记录](https://www.luogu.com.cn/record/34508052) - [P2375 [NOI2014]动物园](https://www.luogu.com.cn/problem/P2375) 题意就是求每个前缀 $\leq$ 长度一半的 $\rm Bd$ 个数。 先跑个`KMP`,建立一棵 `fail` 树，问题相当于询问某个前缀 $u$ 的祖先中 $len$ 值不超过 $len[u]/2$ 的点的个数。 暴力跳`fail`显然不可取。 - 做法一 注意到长度具有单调性，越往上越短。可以倍增，预处理每个点的“深度”即可得到答案。 很不幸，这不是正解，所以需要卡常。 - 做法二 类似 `KMP` 的 `Build` ，在 `fail` 上匹配自身，不同的是，若匹配长度超过 $len[u]/2$ 则停止，复杂度也是均摊 $O(n)$ 的。 模板是黄题而本题(简单小应用)是蓝题，充分体现了大多数人只是背了个板子而已 ( [评测记录](https://www.luogu.com.cn/record/34325751) - [P5829 【模板】失配树](https://www.luogu.com.cn/problem/P5829) 对单串建立一棵 $fail$ 树。 前面说过,某个前缀的 $\rm Bd$ 集合即为 $fail$ 树上一条到根的链。 那么两个前缀的公共 $\rm Bd$ 即为公共祖先，若要求最长，即为 $\rm LCA$。 还有，本题中 $\rm Bd$ 的定义不包括原串，若 ${\rm lca}(u,v)$ 与 $u$ 或 $v$ 重合，还需向祖先跳一步。 本题数据范围较大，若显式地建立树并递归可能会 `MLE`。 [评测记录](https://www.luogu.com.cn/record/34507552) - [P3426 [POI2005]SZA-Template](https://www.luogu.com.cn/problem/P3426) 首先，满足条件的印章一定是个 $\rm Bd$。 查看该 $\rm Bd$ 在原串中的匹配，若完整地覆盖了原串，则可行，否则不可行。 如何求匹配位置呢? 回顾`KMP`的方法，其实就等价于把 $\rm Bd$ 拿到自动机上匹配，若匹配长度达到总长则表明配上了。 又由于 $\rm Bd$ 是原串的前缀，我们没必要对每个 $\rm Bd$ 都匹配一次，可以直接使用原来的匹配信息(即$fail$)。 但是注意，当匹配前缀 $u$ 时，其在 $i\in[1,u]$ 的匹配长度并非 $fail[i]$ ，而是 $i$ 本身(全部匹配)。需要特判一下。 若匹配长度达到当前 $\rm Bd$ 长度，则在这里匹配上了。 于是，从小到大枚举每个 $\rm Bd$ ，设为 $B$ ，称一个前缀 $u$ 合法当且仅当 $fail[u]\geq |B|$ ，即能匹配上。 随着 $|B|$ 的增大，会逐渐删除某些位置，我们使用双向链表维护。顺便维护相邻两次匹配位置的最大差值，若$\leq|B|$ ，则该 $\rm Bd$ 可行。 [评测记录](https://www.luogu.com.cn/record/34508369) - **关于周期和匹配的一些性质** - $\text{\color{blue}定理(2) }\text{Weak Periodicity Lemma :}$ 若 $p,q$ 为 $S$ 的周期，且 $p+q\leq n$ ，则 $\gcd(p,q)$ 也是 $S$ 的周期。（简称为 $\rm WPL$） 不妨设 $p>q$ ，令 $d=p-q$。 当 $i>q$ 时，有 $s[i]=s[i-q]=s[i-q+p]=s[i+d]$ 当 $i<p$ 时，有 $s[i]=s[i+p]=s[i+p-q]=s[i+d]$ 而以上两种情况必然包含所有的 $i$。所以，$d$ 也是 $s$ 的周期。辗转相减即可得到 $\gcd(p,q)$。 强化版 $\text{Periodicity Lemma}$ : $p+q-\gcd(p,q)\leq n\Longrightarrow\gcd(p,q)$ 也是 $S$ 的周期。证明不会。 一般用弱化版就够了。 - $\color{blue}\text{定理(3):}$ 若 $S$ 是 $T$ 的前缀，且 $T$ 有周期 $a$ ， $S$ 有整周期 $b$ ，$b|a,\ |S|\geq a$ ，则 $T$ 也有周期 $b$。 显然成立，看图 ： $\begin{aligned} &\boxed{\qquad\ \ \ {\color{red}|}S\qquad\ |\quad}\qquad\qquad\ \ \ \boxed{\qquad\ \ \ {\color{red}|}S\qquad\ |\quad} \\T:\ &\boxed{\qquad\qquad\qquad|\qquad\qquad\qquad|\qquad\qquad\qquad|\qquad\qquad\qquad|\qquad\qquad\cdots} \\&\qquad\qquad\qquad\ \boxed{\qquad\ \ \ {\color{red}|}S\qquad\ |\quad}\qquad\qquad\ \ \ \boxed{\qquad\ \ \ {\color{red}|}S\qquad\ |\quad} \end{aligned}$ - $\color{blue}\text{定理(4):}$ 若 $S$ 如下图匹配，则表示 $S_1∪S_2$ 有长度为 $d$ 的周期。 $\begin{aligned} &\ \boxed{\qquad\qquad\qquad\qquad T\qquad\qquad\qquad\qquad} \\&\ \boxed{\qquad\qquad\quad S_1\qquad\qquad\quad} \\&\xleftrightarrow[\quad \normalsize d\quad]{}\! \boxed{\quad\qquad\qquad S_2\qquad\quad\qquad} \end{aligned}$ $S$ 有 $|S|-d$ 的 $\rm Bd$，也即 $d$ 的周期。 由于 $S_1,S_2$ 出现位置刚好相差 $d$ ，它们的周期是重合的，所以 $S_1∪S_2$ 也有周期 $d$。 - $\color{blue}\text{定理(5):}$ 若 $2|S|\geq|T|$ ，则 $S$ 在 $T$ 中的匹配位置必为等差序列。 不妨将 $T$ 中没有被匹配覆盖到的（前后）部分去掉，这样 $T$ 中的所有位置都被 $S$ 的匹配覆盖。 显然，若匹配次数 $\leq 2$ ，必为等差数列。 下面来讨论匹配次数达到 $3$ 的情况。设第一，二次匹配间隔长度为 $d$ ，之后的某次匹配与第二次匹配的间隔为 $q$。 $\begin{aligned} &\ \boxed{\qquad\qquad\qquad\qquad\qquad T\qquad\qquad\qquad\qquad\qquad\ \ \ } \\&\ \boxed{\qquad\qquad\quad S_1\qquad\qquad\quad} \\&\xleftrightarrow[\quad\ \normalsize d\quad]{}\! \boxed{\quad\qquad\qquad S_2\qquad\quad\qquad} \\&\qquad\quad\,\,\xleftrightarrow[\qquad\quad\ \normalsize q\quad\qquad]{}\! \boxed{\quad\qquad\qquad S_x\qquad\quad\qquad} \end{aligned}$ 根据 $\color{blue}\text{定理(3)}$ ， $S$ 有周期 $d,q$。 由 $2|S|\geq|T|,\ d+q+|S|=|T|$ 有 $d+q\leq|S|$ ，由 $\rm WPL$ 得 $r=\gcd(d,q)$ 也是 $S$ 的周期。 假设 $S$ 的最小周期为 $p_{\min}$ ，则有 $p\leq r\leq d$ 。若 $p_{\min}\!\not|\ r$ ，由 $\rm WPL$ 可以构造出更小的周期，所以 $p_{\min}|r|d$。 由 $\color{blue}\text{定理(4)}$ , $\color{blue}\text{定理(3)}$，可得 $S_1∪S_2$ 有周期 $p_{\min}$。 若 $p_{\min}<d$ ，则能构造出比 $S_1$ 更靠前的匹配（如下图），所以只能是 $p_{\min}=r=d$。 $\begin{aligned} S_1:\ &\boxed{\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\ \ } \\S_?:\ &\quad\ \ \,\,\boxed{\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\ \ } \\S_2:\ &\!\xleftrightarrow[\quad\ \normalsize d \quad]{}\! \boxed{\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\ \ } \end{aligned}$ 由于 $\gcd(d,q)=r=d\Rightarrow d|q$ ，所有匹配的循环节都是重合的。又因为匹配覆盖了整个 $T$ ，所以 $T$ 拥有和 $S$ 一样的(最小)循环节。 $\begin{aligned} &\!\!\xleftrightarrow{\quad\ \ \normalsize d\quad} \\T:\ &\boxed{\qquad\quad|\qquad\quad|\qquad\quad|\qquad\quad|\qquad\quad|\qquad\quad|\quad} \\S_1:\ &\boxed{\qquad\quad|\qquad\quad|\qquad\quad|\quad} \\S_2:\ &\qquad\quad\,\,\boxed{\qquad\quad|\qquad\quad|\qquad\quad|\quad} \\S_3:\ &\qquad\quad\,\,\qquad\quad\,\,\boxed{\qquad\quad|\qquad\quad|\qquad\quad|\quad} \\S_4:\ &\qquad\quad\,\,\qquad\quad\,\,\qquad\quad\,\,\boxed{\qquad\quad|\qquad\quad|\qquad\quad|\quad} \end{aligned}$ 现在不难发现此时的匹配一定是等差序列。 - **关于 Border 的一些性质** - $\color{blue}\text{定理(6):}$ $S$ 的长度达到 $n/2$ 的 $\rm Bd$ 长度构成一个等差序列。 设长度最大的 $\rm Bd$ 为 $n-p$ ，另一个 $\rm Bd$ 长度为 $n-q$ ，且均有 $p,q\leq n/2$。 由 $\rm WPL$ 得 $\gcd(p,q)$ 也是 $S$ 的周期，所以存在长度为 $n-\gcd(p,q)$ 的 $\rm Bd$。 根据 $n-p$ 为最长 $\rm Bd$ 的假设，要满足 $\gcd(p,q)\geq p$ 即 $p|q$。( 也就是等差了，公差为 $p$ ) 整个等差序列的存在性由周期不难证明。 - $\color{blue}\text{定理(7):}$ 一个串 $S$ 的所有 $\rm Bd$ 按长度排序后,可以被划分成 $O(\log n)$ 个等差序列。 首先，将该串的长度达到 $n/2$ 的 $\rm Bd$ 划分成一个等差序列。 考虑长度达到 $n/2$ 的 $\rm Bd$ 中长度最小的 $T$。 若最小循环节 $d\leq n/4$ ，不断从最长 $\rm Bd$ 减去 $d$ 则必然有 $|T|\leq \frac{3}{4}n$ 。 若 $d>n/4$ ，则最长 $\rm Bd$ 本身就 $\leq \frac{3}{4}n$。 由 $\color{blue}\text{定理(1)}$ ，其余的 $\rm Bd$ 都是 $T$ 的 $\rm Bd$，问题缩小至原来的 $3/4$ 规模。 如此缩小， $O(\log |S|)$ 轮就结束了。实际上，有更紧凑的界 $\lceil \log_2|S|\rceil$，证明从略。 一个达到上界数量级的简易构造 ： $\begin{aligned}&\texttt{abacabadabacaba}\\&\texttt{abacaba}\\&\texttt{aba}\\&\texttt{a}\end{aligned}$ 由上面的证明不难发现，这些等差序列的公差是成倍增长的，所以又有推论 ： - 一个串 $S$ 公差 $\geq d$ 的 $\rm Bd$ 等差序列总大小是 $O(n/d)$ 的。 - $\color{green}{\bf \Delta}$ **例题** ： - [P4156 [WC2016]论战捆竹竿](https://www.luogu.com.cn/problem/P4156) | [Sol](https://www.luogu.com.cn/problem/P4156) - [Loj#6681. yww 与树上的回文串](https://loj.ac/p/6681) | [Sol](https://www.luogu.com.cn/blog/command-block/str-ji-lu-loj6681-yww-yu-shu-shang-di-hui-wen-chuan) - [CF1286E Fedya the Potter Strikes Back](https://www.luogu.com.cn/problem/CF1286E) | [Sol](https://www.luogu.com.cn/blog/command-block/str-ji-lu-cf1286e-fedya-the-potter-strikes-back) - [P5287 [HNOI2019]JOJO](https://www.luogu.com.cn/problem/P5287) 显然,题目需要求的东西就是 $fail$ 的和。 由于保证相邻段字母不相同,所以只能一段段匹配,不存在一段配两段的情况。 而且,除了头和尾,其余的**必须完整匹配**。 考虑把每一段压缩成一个二元组。如 $\texttt{aabbbaabbaabbb}$ ,可以压缩成 $\texttt{(a,2)(b,3)(a,2)(b,2)(a,2)(b,3)}$。 压缩后的 $fail$定义为二元组字符串的 $fail$,而 $flen$ 定义为各个前缀完整匹配的 $\rm Bd$ 长度(加权的 $fail$)。 对于上例,$fail=\{0,0,1,0,1,2\};\ flen=\{0,0,2,0,2,5\}$。 注意,我们认为 $\texttt{(b,2)}$ 和 $\texttt{(b,3)}$ 不匹配。 考虑加上一个二元组 $(z,c)$ 时如何计算贡献。 首先计算出压缩后的 $flen$。 一路跳 $fail$ ,查看对应的出边 $(z',c')$ ,若 $z'=z$ ,匹配长度 $d$ 对 $c'$ 取 $\max$。最终 $d$ 的值不能超过 $c$。 最后,这一段的贡献是以 $flen$ 开始的,长度为 $d+1$ 的,公差为 $1$ 的等差数列。高斯求和即可。 然而,本题要求可持久化,每次暴力跳 $fail$ 复杂度是均摊的,可能会被卡到 $O(n^2)$。 - **做法一** : 可持久化 `KMP` 自动机。 回忆我们建立 $\rm AC$ 自动机的过程,暴力跳 $fail$ 复杂度同样不对,但是我们把 $\rm AC$ 自动机补全成 $\rm Trie$ 图,做到真正的 $O(1)$ 转移,复杂度就正确了。 类似地,我们可以预处理出每个位置的每个字符出边到达的点,称之为`KMP`自动机。 在`KMP`自动机上,可以 $O(1)$ 转移至原来需要暴力跳 $fail$ 才能到达的位置。 由于字符集较大,不能直接暴力写出所有转移。 `build`的过程 : 相当于从上一位的 $fail$ 的某个对应出边,作为该位置的 $fail$。 从父亲处拷贝所有转移,然后修改某一个,这可以使用可持久化线段树维护。 然后再维护答案,对于**每种字母**,维护对应的匹配最长段长度。这可以直接与父亲取 $\min$。 综上,可持久化线段树维护即可。复杂度 $O(n\log n+n\Sigma)$。 - **做法二** : `Border` 树。 我们需要为 $KMP$ 寻找复杂度较为严格的做法。 回忆 : $\rm Bd$ 的长度可以被划分成 $O(\log n)$ 个等差序列。 我们跳 $fail$ 的过程实际上就是在遍历 $\rm Bd$ ,若当中有一串等差序列,那么中间夹着的部分一定是“循环重复”的。 既然是重复的,那也就没必要全部查看,只需要查看最长的,然后直接跳至下一个等差序列即可。 每次跳 $fail$ 的次数严格 $O(\log n)$ ,总跳跃次数就是严格 $O(n\log n)$ 的。 若需要可持久化,使用可持久化数组即可。复杂度 $O(n\log^2n)$。 注意到本题并没有要求强制在线,可以将操作树离线下来,将问题转化成一系列的修改和回退操作。 最终采用做法二的离线版本,复杂度为 $O(n\log n)$。 ```cpp ``` - **最小后缀 Significant Suffixes** - $\color{blue}\text{定义:}$ 记 ${\rm suf}(S)$ 为 $S$ 的后缀集合。 记 ${\rm minsuf}(S)$ 为 $S$ 的最小后缀。 记 ${\rm Ssuf}(S)$ 为 $\{V\in {\rm suf}(S)\big|∃T, VT={\rm minsuf}(ST)\}$ ，意思就是说，在 $S$ 后面加一个串之后，可能称为最小后缀的后缀。即 $\rm Significant Suffixes$，简称为 $\rm Ssuf$。 - $\color{blue}\text{定理(8):}$ 对于任意两个 ${\rm Ssuf}\ U,V$ ，$|U|<|V|\Rightarrow U$ 是 $V$ 的前缀。 若 $U$ 并非 $V$ 的前缀，无论向串后面加怎样的 $T$，$UT$ 和 $VT$ 的大小关系还是由 $U,V$ 的大小关系决定。 所以 $U,V$ 只有一者有可能是 ${\rm Ssuf}$，矛盾。 注意，$U$ 同时也是 $V$ 的后缀，所以 $U$ 是 $V$ 的 $\rm Bd$。 - $\color{blue}\text{定理(9):}$ 若串 $S$ 有两个 ${\rm Ssuf}\ U,V$ 满足 $|U|<|V|$ ，则 $2|U|<|V|$ 假设 $|U|<|V|<2|U|$ ，由 $\color{blue}\text{定理(8)}$ 可得 $U$ 是 $V$ 的 $\rm Bd$。 即对应长度为 $|V|-|U|<|U|,|V|/2$ 的周期。设一个周期为 $T$ ，令 $U=TC,V=TTC$。 假设在后面加了 $R$（可空） 后，有 $UR<VR$ 即 $TCR<TTCR$ ，则 $CR<TCR$ ，所以 $UR$ 注定不可能是最小后缀，矛盾。 推论 ：$|{\rm Ssuf}(S)|\leq O(\log |S|)$。 - $\color{green}{\bf \Delta}$ **例题** ：[P5211 [ZJOI2017]字符串](https://www.luogu.com.cn/problem/P5211) | [Sol](https://www.luogu.com.cn/blog/command-block/str-ji-lu-p5211-zjoi2017-zi-fu-chuan)