前缀计算法

1. 前缀函数

前缀 是指从串首开始到某个位置 结束的一个特殊子串。字符串 的以 结尾的前缀表示为
真前缀 指除了 本身的 的前缀。

后缀 是指从某个位置 开始到整个串末尾结束的一个特殊子串。字符串 的从 开头的后缀表示为
真后缀 指除了 本身的 的后缀。

给定一个长度为 的字符串 ，其 前缀函数 定义为一个长度为 的数组 。其中 含义为：

对于字符串 和 ，若 对于所有 成立，则称 是 的 周期 。

对于字符串 和 ，若 长度为 的前缀和长度为 的后缀相等，就称 长度为 的前缀（后缀）是 的 border 。

【注】易知前缀函数 对应的就是字符串 的最长 border 的长度。

根据前缀函数的定义我们可以发现，相邻的前缀函数值至多增加 1 ，故可以得到字符串 的前缀函数的计算公式：

【注】计算字符串的前缀函数的思想和 KMP 算法中计算字符串失配数组的思想非常相似。

前缀函数可以用来实现 KMP 算法，思路为：拼接模式串 和主串 ，得到 ， 为不在 和 中出现的字符。设 计算拼接后的字符串 的前缀函数，当出现 时，说明此时模式串匹配上了主串的子串 。

整个算法时间复杂度为 。

根据上文中给出的性质，可以很容易求出字符串 的字符串周期 & border。假设 ，则可以在 时间内求出 的所有周期 & border。

给定字符串 ，其长度 ，计算 中不同的子串的数目。

【注】从头部添加、头部移除或尾部移除后计算不同子串的思想类似。

根据上文的性质可知，如果计算出 的前缀函数之后， 的最小周期为 。由字符串的周期的定义可知，最后字符串 删去每段周期长度的字符串后，剩余的最后一段字符串长度不一定是 。故如果 ，则 即是 的长度，否则不存在一个有效的压缩，即 的长度为 。