1. 定义
1.1 前缀 & 真前缀
前缀是指从串首开始到某个位置 结束的一个特殊子串。字符串 的以 结尾的前缀表示为
真前缀指除了 本身的 的前缀。
1.2 后缀 & 真后缀
后缀是指从某个位置 开始到整个串末尾结束的一个特殊子串。字符串 的从 开头的后缀表示为
真后缀指除了 本身的 的后缀。
1.3 前缀函数
给定一个长度为 的字符串 ,其前缀函数定义为一个长度为 的数组 。其中 含义为:
- 如果子串 有相等的真前缀 和真后缀 ,那么 为最大的相等的真前后缀长度,即
- 如果子串 没有相等的真前后缀,则
1.4 字符串的周期
对于字符串 和 ,若 对于所有 成立,则称 是 的周期。
1.5 字符串的 border
对于字符串 和 ,若 长度为 的前缀和长度为 的后缀相等,就称 长度为 的前缀(后缀)是 的 border 。
【注】易知前缀函数 对应的就是字符串 的最长 border 的长度。
2. 性质
如果字符串 有长度为 的 border,则 是 的周期。
如果字符串 的前缀函数为 ,,则:
- 所有的 border 长度为 。
- 所有的周期为 。
- 是 的最长 border 的长度, 是 的最小周期。
3. 实现
根据前缀函数的定义我们可以发现,相邻的前缀函数值至多增加 1 ,故可以得到字符串 的前缀函数的计算公式:
- 。
- 如果 ,则
- 如果 ,令 。若 ,则令 ,直到 为止,则
【注】计算字符串的前缀函数的思想和 KMP 算法中计算字符串失配数组的思想非常相似。
4. 应用
4.1 KMP
前缀函数可以用来实现 KMP 算法,思路为:拼接模式串 和主串 ,得到 , 为不在 和 中出现的字符。设 计算拼接后的字符串 的前缀函数,当出现 时,说明此时模式串匹配上了主串的子串 。
整个算法时间复杂度为 。
4.2 字符串周期 & border
根据上文中给出的性质,可以很容易求出字符串 的字符串周期 & border。假设 ,则可以在 时间内求出 的所有周期 & border。
4.3 统计每个前缀出现次数
- 统计字符串 的所有前缀子串在 中出现的次数,。
- 首先统计前缀数组值 , 表示字符串 最长相等真前后缀长度,即说明前缀 在 中出现了 1 次(不包括前缀本身)。
- 前缀数组值统计后,只统计出了每个前缀作为某个字符串 的最长真后缀的出现次数,而没有统计非最长真后缀的出现次数,故根据 数组的性质统计非最长真后缀的出现次数。
- 加上每个前缀本身 1 次。
ll ans[MAXN]; // 对应长度的前缀在字符串中出现的次数
void getAns(ll m) {
// ans[0] 没有实际意义
for(ll i = 0; i < m; ++i) ++ans[pi[i]];
for(ll i = m-1; i; --i) ans[pi[i-1]] += ans[i];
for(ll i = 0; i <= m; ++i) ++ans[i];
}
- 统计字符串 的所有前缀子串在 中出现的次数, 。拼接字符串 和 ,使得 。
- 首先统计前缀数组值 , 表示字符串 最长相等真前后缀长度,即说明前缀 在 中出现了 1 次(不包括前缀本身),易知最长真前后缀都不会包含界定符 ,故统计得到的只是字符串 中的。
- 前缀数组值统计后,只统计出了每个前缀作为某个字符串 的最长真后缀的出现次数,而没有统计非最长真后缀的出现次数,故根据 数组的性质统计非最长真后缀的出现次数。
ll ans[MAXN]; // 对应长度的前缀在字符串中出现的次数
void getAns(ll m, ll n) {
// ans[0] 没有实际意义
// 只统计字符串 t 中的
for(ll i = m+1; i < n+m+1; ++i) ++ans[pi[i]];
for(ll i = m; i; --i) ans[pi[i-1]] += ans[i];
}
4.4 不同子串数目
给定字符串 ,其长度 ,计算 中不同的子串的数目。
- 设字符串 的不同子串数目为 ,则向 末尾添加一个字符后得到字符串 。显然 的子串中可能会出现一些新的以 结尾的子串。
- 反转字符串 得到字符串 ,则问题变成统计以 开头且未在 的其他地方出现的前缀数目。
- 设 的前缀函数的最大值为 ,则最长的出现在 其他地方的前缀长度为 ,故更短的前缀也一定出现了。
- 因此,字符串 新增一个末尾字符 后新出现的子串的数目为 。
【注】从头部添加、头部移除或尾部移除后计算不同子串的思想类似。
4.5 字符串压缩
- 给定字符串 ,其长度 ,我们希望找到一个最短的字符串 ,使得 为 的一份或多份拷贝的拼接表示。
- 显然,我们只需要找到 的长度即可,该问题的答案即为长度为该值的 的前缀。
根据上文的性质可知,如果计算出 的前缀函数之后, 的最小周期为 。由字符串的周期的定义可知,最后字符串 删去每段周期长度的字符串后,剩余的最后一段字符串长度不一定是 。故如果 ,则 即是 的长度,否则不存在一个有效的压缩,即 的长度为 。
5. 代码
#include <bits/stdc++.h>
using namespace std;
// 前缀函数
struct PrefixFunction {
#ifndef _PREFIXFUNCTION_
#define ll int
#define MAXN 1000005
#endif
ll cnt; // 字符串的 border(或周期)个数
ll pi[MAXN]; // 前缀函数
ll border[MAXN]; // border 长度数组(从大到小)
ll period[MAXN]; // 周期数组(从小到大)
PrefixFunction(): cnt(0) {}
// 计算前缀函数
void getPi(char *str, ll n) {
pi[0] = 0;
ll i = 1, j = pi[i-1];
while(i < n) {
if(str[i] == str[j]) {
pi[i++] = j++ + 1;
} else if(!j) {
pi[i++] = j;
} else {
j = pi[j-1];
}
}
}
// 计算所有 border 的长度
void getBorder(ll n) {
ll count = 0;
ll j = pi[n-1];
while(j) {
border[count++] = j;
j = pi[j-1];
}
cnt = count;
}
// 计算所有周期
void getPeriod(ll n) {
ll count = 0;
ll j = pi[n-1];
while(j) {
period[count++] = n - j;
j = pi[j-1];
}
cnt = count;
}
};