前缀函数

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..∣S∣−1]\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..kj−1]s[0..k_j-1] 和真后缀 s[i−(kj−1)..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 字符串的周期

对于字符串 ss 和 0<p≤∣s∣0 \lt p \leq |s|，若 s[i]=s[i+p] s[i] = s[i+p] 对于所有 i∈[0,∣s∣−p−1] i \in [0, |s|-p-1] 成立，则称 pp 是 ss 的周期。

1.5 字符串的 border

对于字符串 ss 和 0≤r<∣s∣0 \leq r \lt |s|，若 ss 长度为 rr 的前缀和长度为 rr 的后缀相等，就称 ss 长度为 rr 的前缀（后缀）是 ss 的 border 。

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

2. 性质

  • 如果字符串 ss 有长度为 rr 的 border，则 ∣s∣−r|s| - r 是 ss 的周期。

  • 如果字符串 ss 的前缀函数为 π\pi，∣s∣=n |s| = n ，则：

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

3. 实现

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

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

  • 如果 s[i]=s[π[i−1]]s[i] = s[\pi[i-1]]，则

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

  • 如果 s[i]≠s[π[i−1]]s[i] \ne s[\pi[i-1]]，令 j=π[i−1] j = \pi[i-1] 。若 s[i]≠s[j] s[i] \ne s[j] ，则令 j=π[j−1] j = \pi[j-1] ，直到 j=0∨s[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，#\# 为不在 ss 和 tt 中出现的字符。设

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

计算拼接后的字符串 SS 的前缀函数，当出现 i>m∧π[i]=mi \gt m \wedge \pi[i] = m 时，说明此时模式串匹配上了主串的子串 ti−2m⋯ti−m−1t_{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=∣s∣m = |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=∣t∣m = |s|, n = |t| 。拼接字符串 ss 和 tt，使得 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，使得 ss 为 tt 的一份或多份拷贝的拼接表示。

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

根据上文的性质可知，如果计算出 ss 的前缀函数之后，ss 的最小周期为 k=n−π[n−1]k = n - \pi[n-1]。由字符串的周期的定义可知，最后字符串 ss 删去每段周期长度的字符串后，剩余的最后一段字符串长度不一定是 kk。故如果 k∣nk | 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