前缀函数

1. 定义

1.1 前缀 & 真前缀

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

prefix(S,i)=S[0..i]\begin{array}{c} prefix(S,i) = S[0..i] \end{array}

真前缀指除了 SS 本身的 SS 的前缀。

1.2 后缀 & 真后缀

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

suffix(S,i)=S[i..S1]\begin{array}{c} suffix(S,i) = S[i..|S|-1] \end{array}

真后缀指除了 SS 本身的 SS 的后缀。

1.3 前缀函数

给定一个长度为 nn 的字符串 ss,其前缀函数定义为一个长度为 nn 的数组 π\pi。其中 π[i]\pi[i] 含义为:

  • 如果子串 s[0..i]s[0..i] 有相等的真前缀 s[0..kj1]s[0..k_j-1] 和真后缀 s[i(kj1)..i]s[i-(k_j-1)..i],那么 π\pi 为最大的相等的真前后缀长度,即

π[i]=max{kj}\begin{array}{c} \pi[i] = max\{k_j\} \end{array}

  • 如果子串 s[0..i]s[0..i] 没有相等的真前后缀,则

π[i]=0\begin{array}{c} \pi[i] = 0 \end{array}

1.4 字符串的周期

对于字符串 ss0<ps0 \lt p \leq |s|,若 s[i]=s[i+p] s[i] = s[i+p] 对于所有 i[0,sp1] i \in [0, |s|-p-1] 成立,则称 ppss周期

1.5 字符串的 border

对于字符串 ss0r<s0 \leq r \lt |s|,若 ss 长度为 rr 的前缀和长度为 rr 的后缀相等,就称 ss 长度为 rr 的前缀(后缀)是 ssborder

【注】易知前缀函数 π[i]\pi[i] 对应的就是字符串 s[0..i]s[0..i] 的最长 border 的长度。

2. 性质

  • 如果字符串 ss 有长度为 rr 的 border,则 sr|s| - rss 的周期。

  • 如果字符串 ss 的前缀函数为 π\pis=n |s| = n ,则:

  1. ss 所有的 border 长度为 π[n1],π[π[n1]1], \pi[n-1],\pi[\pi[n-1]-1],\cdots
  2. ss 所有的周期为 nπ[n1],nπ[π[n1]1], n-\pi[n-1],n-\pi[\pi[n-1]-1],\cdots
  3. π[n1]\pi[n-1]ss 的最长 border 的长度,nπ[n1]n - \pi[n-1]ss 的最小周期。

3. 实现

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

  • s[0]=0s[0] = 0

  • 如果 s[i]=s[π[i1]]s[i] = s[\pi[i-1]],则

π[i]=π[i1]+1\begin{array}{c} \pi[i] = \pi[i-1] + 1 \end{array}

  • 如果 s[i]s[π[i1]]s[i] \ne s[\pi[i-1]],令 j=π[i1] j = \pi[i-1] 。若 s[i]s[j] s[i] \ne s[j] ,则令 j=π[j1] j = \pi[j-1] ,直到 j=0s[i]=s[j] j = 0 \vee s[i] = s[j] 为止,则

π[i]={0if s[i]s[j]j+1if s[i]=s[j]\begin{array}{c} \pi[i] = \begin{cases} 0 & if \ s[i] \ne s[j] \\ j + 1 & if \ s[i] = s[j] \end{cases} \end{array}

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

4. 应用

4.1 KMP

前缀函数可以用来实现 KMP 算法,思路为:拼接模式串 ss 和主串 tt,得到 S=s+#+tS = s + \# + t#\# 为不在 sstt 中出现的字符。设

m=sn=t\begin{array}{c} m = |s| \\ n = |t| \end{array}

计算拼接后的字符串 SS 的前缀函数,当出现 i>mπ[i]=mi \gt m \wedge \pi[i] = m 时,说明此时模式串匹配上了主串的子串 ti2mtim1t_{i-2m} \cdots t_{i-m-1}

整个算法时间复杂度为 O(n+m)O(n+m)

4.2 字符串周期 & border

根据上文中给出的性质,可以很容易求出字符串 ss 的字符串周期 & border。假设 s=m|s| = m,则可以在 O(m)O(m) 时间内求出 ss 的所有周期 & border。

4.3 统计每个前缀出现次数

  • 统计字符串 ss 的所有前缀子串在 ss 中出现的次数,m=sm = |s|
  1. 首先统计前缀数组值 π[i]\pi[i]π[i]\pi[i] 表示字符串 s[0..i]s[0..i] 最长相等真前后缀长度,即说明前缀 s[0..π[i]1]s[0..\pi[i]-1]s[0..i]s[0..i] 中出现了 1 次(不包括前缀本身)。
  2. 前缀数组值统计后,只统计出了每个前缀作为某个字符串 s[0..i]s[0..i] 的最长真后缀的出现次数,而没有统计非最长真后缀的出现次数,故根据 π\pi 数组的性质统计非最长真后缀的出现次数。
  3. 加上每个前缀本身 1 次。
1
2
3
4
5
6
7
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];
}
  • 统计字符串 ss 的所有前缀子串在 tt 中出现的次数,m=s,n=tm = |s|, n = |t| 。拼接字符串 sstt,使得 S=s+#+tS = s + \# + t
  1. 首先统计前缀数组值 π[i],i>m\pi[i], i \gt mπ[i]\pi[i] 表示字符串 S[0..i]S[0..i] 最长相等真前后缀长度,即说明前缀 S[0..π[i]1]S[0..\pi[i]-1]S[0..i]S[0..i] 中出现了 1 次(不包括前缀本身),易知最长真前后缀都不会包含界定符 #\#,故统计得到的只是字符串 tt 中的。
  2. 前缀数组值统计后,只统计出了每个前缀作为某个字符串 S[0..i]S[0..i] 的最长真后缀的出现次数,而没有统计非最长真后缀的出现次数,故根据 π\pi 数组的性质统计非最长真后缀的出现次数。
1
2
3
4
5
6
7
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 不同子串数目

给定字符串 ss,其长度 s=m|s| = m,计算 ss 中不同的子串的数目。

  • 设字符串 s[0..i]s[0..i] 的不同子串数目为 kk,则向 s[0..i]s[0..i] 末尾添加一个字符后得到字符串 s[0..i+1]s[0..i+1]。显然 s[0..i+1]s[0..i+1] 的子串中可能会出现一些新的以 s[i+1]s[i+1] 结尾的子串。

  • 反转字符串 s[0..i+1]s[0..i+1] 得到字符串 tt,则问题变成统计以 s[i+1]s[i+1] 开头且未在 tt 的其他地方出现的前缀数目。

  • tt 的前缀函数的最大值为 πmax\pi_{max},则最长的出现在 tt 其他地方的前缀长度为 πmax\pi_{max},故更短的前缀也一定出现了。

  • 因此,字符串 ss 新增一个末尾字符 s[i+1]s[i+1] 后新出现的子串的数目为 s+1πmax|s| + 1 - \pi_{max}

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

4.5 字符串压缩

  • 给定字符串 ss,其长度 s=n|s| = n,我们希望找到一个最短的字符串 tt,使得 sstt 的一份或多份拷贝的拼接表示。

  • 显然,我们只需要找到 tt 的长度即可,该问题的答案即为长度为该值的 ss 的前缀。

根据上文的性质可知,如果计算出 ss 的前缀函数之后,ss 的最小周期为 k=nπ[n1]k = n - \pi[n-1]。由字符串的周期的定义可知,最后字符串 ss 删去每段周期长度的字符串后,剩余的最后一段字符串长度不一定是 kk。故如果 knk | n,则 kk 即是 tt 的长度,否则不存在一个有效的压缩,即 tt 的长度为 nn

5. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

#ifndef _PREFIXFUNCTION_
#define _PREFIXFUNCTION_
#define ll int
#define MAXN 1000005

// 前缀函数
struct PrefixFunction {
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;
}
};
#endif

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!