前言
这是一个咕了将近半年的文章，并不需要什么前置知识，只需要看的懂一些数学表达式就好了。
符号约定
- \(|S|\)表示字符串\(S\)的长度。
- \(S[l...r]\)表示由第\(l\)个到\(r\)个字符组成的\(S\)的子串，位置由\(1\)开始。
- \(\mathrm{Suf}(S)\)表示字符串\(S\)的所有后缀构成的集合，\(\mathrm{Suf'}(S)\)表示除去自身的所有后缀构成的集合, \(\mathrm{Suf}(S,l)\)表示\(S\)长度为\(l\)的后缀。
- \(\mathrm{Pre}(S),\mathrm{Pre'}(S), \mathrm{Pre}(S, l)\)同理。
讲解
\(\mathrm{Border}\)
用\(\mathrm{Border}(S)\)表示字符串\(S\)相同前缀后缀构成的集合（这里用他们的长度记录）。用形式化的表示就是：
对于\(l\in \mathrm{Border}(S)\)，我们称\(\mathrm{Pre}(S,l)\)或\(\mathrm{Suf}(S,l)\)为\(S\)的\(\mathrm{Border}\)，可以发现，空串是所有串的\(\mathrm{Border}\)。
可以发现一个简单的性质：
这个比较显然，用通俗语言概括就是我的\(\mathrm{Border}\)的\(\mathrm{Border}\)是我的\(\mathrm{Border}\)。
用\(\mathrm{fail}(S)\)表示最长\(\mathrm{Border}\)，形式化就是(很蠢）：
接着找一下规律：
那么可以发现，存在
那么我们能否通过\(\mathrm{fail}(S)\)找到所有的\(\mathrm{Border}\)呢，答案是可行的，至于证明，用反证法搞一搞就好了，没什么难的。
求解\(\mathrm{fail}\)
容易想到\(O(n^2)\)的做法，由于太简单就不贴出来了，因为我们需要\(O(n)\)的。
首先可以发现，假设我们求出了字符串\(S\)中长度为\(1...n\)的所有前缀的\(\mathrm{fail}(\mathrm{Pre}(S,i))\)，那么很明显，\(\mathrm{fail}(\mathrm{Pre}(S,i+1))\)最多只会增加\(1\)，否则就是不断缩小了，而具体怎么缩小，本来需要查看\(\mathrm{Border}(S_i)\)中所有的值，看看是否有能够拓展的，但是按照我们先前得到的性质，只需要往回找到一个\(\mathrm{fail}(\mathrm{Pre}(S,j))\)（设为\(t\)），满足\(S_{t+1}=S_{i+1}\)或者\(j=0\)即可。
容易想到代码实现(这里的\(S\)变成了\(T\)):
n = strlen(T + 1), fail[1] = 0;
for (int i = 2, j = 0; i <= n; i++) {
while(j && T[i] != T[j + 1]) j = fail[j];
if (T[i] == T[j + 1]) j++;
fail[i] = j;
}
求匹配
现在我们对模式串\(T\)求出了\(\mathrm{fail}\)，现在要用\(T\)来匹配\(S\)，那么我们可以使用类似的代码进行匹配：
m = strlen(S + 1);
for (int i = 1, j = 0; i <= m; i++) {
while(j && (S[i] != T[j + 1] || j == n)) j = fail[j];
if (S[i] == T[j + 1]) j++;
f[i] = j; // 如果f[i]==n 则表示S[i-n+1...i]=T
}
\(\mathrm{fail~Tree}\)
对于一个字符串\(S\)的所有前缀，我们都计算出了他们的\(\mathrm{fail}\)。现在我们转换一下定义\(\mathrm{fail}(i)\)表示\(\mathrm{Pre}(S,i)\)的最长\(\mathrm{Border}\)。容易想到构建一颗\(\mathrm{fail}\)树，其中儿子指向父亲的边可以表示为\(i\longrightarrow \mathrm{fail}(i)\)，显然根据这个定义，一个点到跟的路径上的所有点（不包括自己）都是这个点所代表的前缀的\(\mathrm{Border}\)，且他们的长度随着深度的减小而减小。那么可以发现，在这颗树上，两个点的LCA就是这两个点所代表的前缀的最长公共\(\mathrm{Border}\)。
例题
Power Strings
求一个字符串由多少个重复的子串连接而成，也就是求循环节的循环次数。
例如 ababab 由三个 ab 连接而成，abcd 由一个 abcd 连接而成。
容易想到使用\(\mathrm{fail}\)的奇怪性质，假设\(\mathrm{fail}(n)\leq \lfloor\frac{n}{2}\rfloor\)，那么我们画一个图:
因为\(\mathrm{Border}\)的性质，可以得到：
就这样不停地用\(\mathrm{Pre}(S,n-\mathrm{fail}(n))\)填充\(S\)，假如剩下了一节长度小于\(n-\mathrm{fail}(n)\)的，那么就一定无解。
若恰好可以填满，那么我们可以证明，\(\mathrm{Pre}(S,n-\mathrm{fail}(n))\)一定是\(S\)最小的循环节。
那么差不多可以得到问题的答案啦：
[NOI2014]动物园
给定\(N\)个字符串，对于每一个字符串，算出它每一个前缀\(\mathrm{Pre}(S,i)\)不超过该前缀一半的\(\mathrm{Border}\)的数量，称为\(\mathrm{num}(i)\)。你需要将每一个前缀的\(\mathrm{num}(i)+1\)乘起来，作为字符串\(S\)的答案。答案对\(10^9+7\)取模。
我们只需要将\(\mathrm{num}(i)\)都求出来就好了。
很显然，\(\mathrm{num}(i)\)一定是\(\mathrm{fail}(i)\)在\(\mathrm{fail~Tree}\)上的一个祖先，那么最暴力的方法就是对于每一个前缀，暴力地找符合条件的点。
但是数组开不下，而且很容易\(TLE\),那么就需要\(O(n)\)的方法了。
首先在求\(\mathrm{fail}\)的时候，顺道求出\(i\)在\(\mathrm{fail~Tree}\)上到根路径上的节点个数（包括\(i\)自身），这里设为\(cnt_i\)。那么显然，\(\mathrm{num}(i)\)就是到根路径上的某个\(cnt_j\)。接着我们可以发现，\(\mathrm{num}(i)\)每右移一位的时候，至多增加\(1\)，也就是说，我们可以使用类似匹配文本串的方式，加一个小判断，进而求出\(j\)。
for (int i = 2, j = 0; i <= n; i++) {
while (j && str[i] != str[j+1]) j = fail[j];
if (str[i] == str[j+1]) j++;
if ((j<<1) > i) j = fail[j]; // j至多增加1,也就是说至多跳到i/2+1
ans = ans * (cnt[j] + 1) % MOD;
}