字符串基础
基础定义：
字符串：一个由若干个字符组成的序列，通常写作 $S$。
字符串长度：字符串序列的大小，通常写作 $|S|$。
字符：字符串的某一个字符，通常写作 $S[i]$（虽然 string 从 $0$ 开始，但在书面中，通常认为从 $1$ 开始）
子串：字符串的某一段连续子序列，通常写作 $S[l,r]$。
前缀：从 $S[1]$ 开始的一段连续子序列，通常写作 $pre[i]=S[1,i]$。
后缀：从 $S[|S|]$ 结束的一段连续子序列（长度为 $i$），通常写作 $suf[i]=S[|S|-i+1,|S|]$。
重要定义：
Border：若 $pre[i]=suf[i]$，则称 $pre[i]$ 为 $S$ 的一个 Border（有时 Border 也指 $|pre[i]|$ 而不是一个具体的字符串）。
周期：若 $S[i]=S[i-p](i\in [p+1,|S|])$，则称 $p$ 为 $S$ 的周期。
循环节：若周期 $p\mid |S|$，则称 $p$ 为 $S$ 的循环节。
性质：
$p$ 是 $S$ 的周期，$|S|-p$ 是 $S$ 的 $Border$。
结合字符串哈希，可以 $O(1)$ 判断一个数是否是字符串周期。
Border 的求法：
（一般而言，仅考虑一个字符串 $S$ 的 Border 时指的是不含 $S$ 本身的最大 Border）
引理：Border 的 Border 也是 Border。
假设已经求出了 $S[1,i]$ 的 Border，对于新的字符 $S[i+1]$，$S[1,i+1]$ 的 border 一定是 $S[1,i]$ 的 Border，所以只要枚举 $S[1,i]$ 的 Border(pre[j])，判断 $S[pre[j]+1]$ 和 $S[i+1]$ 是否相同即可。枚举 $S[1,i]$ 的 Border 就可以采用 Border 的 Border 还是 Border 的方式来实现了。
时间复杂度：$O(n)$。
因为在枚举 $S[1,i]$ 的 Border 的过程中，Border 对应的 $suf[j]$ 的 $j$ 是在不断变大的。和 $i$ 一样，$j$ 最多从 $1$ 增长到 $n$。所以总时间复杂度还是 $O(n)$ 的。