字符串 hash 数字工具 小质数：101, 103, 1009, 10007, 10009, 100003, 1000003, 1145141 大质数：998244353, 1000000007, 1000000009 kmp 和 border 性质 fail 树子树里的位置为该 border 的出现位置。 性质1. border 的 border 还是 border，并且每次取最大的 border 可以遍历原串所有 border。 性质2. （弱周期引理） 对于周期 $p, q$，如果 $p + q \le n$，则 $gcd(p, q)$ 也是周期。 性质3. 对于字符串 $s, t$，$s$ 为 $t$ 的前缀，$t$ 有周期 $a$，$s$ 有周期 $b$，满足 $a \le |s|$ 且 $b \mid a$，则 $b$ 也为 $t$ 的周期。 性质4. 对于字符串 $s, t$，若 $2|s| \ge |t|$，则 $s$ 在 $t$ 上的匹配位置形成等差数列。 ...