Border
如果字符串 \(S\) 的同长度的前缀和后缀完全相同，即 \(Prefix[i] = Suffix[i]\)
则称此前缀（后缀）为一个 \(Border\)（根据语境，有时 \(Border\) 也指长度）。
特殊地，字符串本身也可以是它的 \(Border\)，具体是不是根据语境判断。
周期和循环节
对于字符串 \(S\) 和正整数 \(p\)，如果有 \(S[i] = S[i − p]\)，对于 \(p < i ≤ |S|\) 成
立，则称 \(p\) 为字符串 \(S\) 的一个周期。
特殊地，\(p = |S|\) 一定是 \(S\) 的周期
若字符串 \(S\) 的周期 \(p\) 满足 \(p \:\: |\:\: |S|\)，则称 \(p\) 为 \(S\) 的一个循环节
特殊地，\(p = |S|\) 一定是 \(S\) 的循环节
重要性质
Border vs 周期
\(p\) 是 \(S\) 的周期 ⇔ \(|S| − p\) 是 \(S\) 的 \(Border\)
证明
\(p 为 S 的周期 ⇔ S[i − p] = S[i]\)
\(q 为 S 的 Border ⇔ S[1, q] = S[|S| − q + 1, |S|] ⇔
S[1] = S[|S| − q + 1], S[2] = S[|S| − q + 2], . . . , S[q] = S[|S|]\)
\(所以|S|-q是一个周期\)
\(易得：p + q = |S|\)
因此，字符串的周期性质等价于 \(Border\) 的性质，
求周期也等价于求 \(Border\)。
警告：\(Border\) 不具有二分性。
Border 的传递性
\(S\) 的 \(Border\) 的 \(Border\) 也是 \(S\) 的 \(Border\)
求 \(S\) 的所有 \(Border\) 等价于求所有前缀的最大 \(Border\)
KMP
next数组
\(next[i]=Preffix[i]\)的非平凡（去掉字符串本身）的最大\(Border\)
\(next[1]=0\)
考虑 \(Prefix[i]\) 的所有（长度大于 \(1\) 的）\(Border\)，去掉最后一个字母，就
会变成 \(Prefix[i − 1]\) 的 \(Border\)。
因此求 \(next[i]\) 的时候，可以遍历 \(Prefix[i − 1]\) 的所有 \(Border\)，即
\(next[i − 1], next[next[i − 1]], . . . , 0，\)检查后一个字符是否等于 \(S[i]\)。
复杂度分析
\(考虑使用势能分析进行讨论：\)
\(如果 next[i] = next[i − 1] + 1，则势能会增加 1\)
\(否则势能会先减少到某个 next[j]，然后有 next[i] = next[j] + 1，势能
也会增加 1，在寻找 next[j] 的过程中，势能会减少，每次至少减少
1。\)
\(还有一种情况，next[i] = 0，势能清空，且不会增加。\)
\(综上，势能总量为 O(N)，因此整体的复杂度也是 O(N)，常数为 2 左右
（很小）。空间复杂度也为 O(N)。\)
实现
void init(string s){
//s="!"+s' 使得s从[1,len]
len=s.length()-1;
t=s;
for(int i=2;i<=len;i++){
nxt[i]=nxt[i-1];
while(nxt[i] && s[i]!=s[nxt[i]+1])nxt[i]=nxt[nxt[i]];
nxt[i]+=(s[i]==s[nxt[i]+1]);
}
return ;
}