前缀函数 - 简书

1. 定义

1.1 前缀 & 真前缀

前缀是指从串首开始到某个位置 $i$ 结束的一个特殊子串。字符串 $S$ 的以 $i$ 结尾的前缀表示为 $prefix(S,i) = S[0..i]$
真前缀指除了 $S$ 本身的 $S$ 的前缀。

1.2 后缀 & 真后缀

后缀是指从某个位置 $i$ 开始到整个串末尾结束的一个特殊子串。字符串 $S$ 的从 $i$ 开头的后缀表示为 $suffix(S,i) = S[i..|S|-1]$
真后缀指除了 $S$ 本身的 $S$ 的后缀。

1.3 前缀函数

给定一个长度为 $n$ 的字符串 $s$ ，其前缀函数定义为一个长度为 $n$ 的数组 $\pi$ 。其中 $\pi[i]$ 含义为：

如果子串 $s[0..i]$ 有相等的真前缀 $s[0..k_j-1]$ 和真后缀 $s[i-(k_j-1)..i]$ ，那么 $\pi$ 为最大的相等的真前后缀长度，即 $\pi[i] = max\{ k_j \}$
如果子串 $s[0..i]$ 没有相等的真前后缀，则 $\pi[i] = 0$

1.4 字符串的周期

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

1.5 字符串的 border

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

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

2. 性质

如果字符串 $s$ 有长度为 $r$ 的 border，则 $|s| - r$ 是 $s$ 的周期。
如果字符串 $s$ 的前缀函数为 $\pi$ ， $|s| = n$ ，则：

$s$ 所有的 border 长度为 $\pi[n-1],\pi[\pi[n-1]-1],\cdots$ 。

$s$ 所有的周期为 $n-\pi[n-1],n-\pi[\pi[n-1]-1],\cdots$ 。

$\pi[n-1]$ 是 $s$ 的最长 border 的长度， $n - \pi[n-1]$ 是 $s$ 的最小周期。

3. 实现

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

$s[0] = 0$ 。
如果 $s[i] = s[\pi[i-1]]$ ，则 $\pi[i] = \pi[i-1] + 1$
如果 $s[i] \ne s[\pi[i-1]]$ ，令 $j = \pi[i-1]$ 。若 $s[i] \ne s[j]$ ，则令 $j = \pi[j-1]$ ，直到 $j = 0 \vee s[i] = s[j]$ 为止，则 $\pi[i] = \begin{cases} 0 & if \ s[i] \ne s[j] \\ j + 1 & if \ s[i] = s[j] \end{cases}$

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

4. 应用

4.1 KMP

前缀函数可以用来实现 KMP 算法，思路为：拼接模式串 $s$ 和主串 $t$ ，得到 $S = s + \# + t$ ， $\#$ 为不在 $s$ 和 $t$ 中出现的字符。设 $m = |s| \\ n = |t|$ 计算拼接后的字符串 $S$ 的前缀函数，当出现 $i \gt m \wedge \pi[i] = m$ 时，说明此时模式串匹配上了主串的子串 $t_{i-2m} \cdots t_{i-m-1}$ 。

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

4.2 字符串周期 & border

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

4.3 统计每个前缀出现次数

统计字符串 $s$ 的所有前缀子串在 $s$ 中出现的次数， $m = |s|$ 。

首先统计前缀数组值 $\pi[i]$ ， $\pi[i]$ 表示字符串 $s[0..i]$ 最长相等真前后缀长度，即说明前缀 $s[0..\pi[i]-1]$ 在 $s[0..i]$ 中出现了 1 次（不包括前缀本身）。

前缀数组值统计后，只统计出了每个前缀作为某个字符串 $s[0..i]$ 的最长真后缀的出现次数，而没有统计非最长真后缀的出现次数，故根据 $\pi$ 数组的性质统计非最长真后缀的出现次数。

加上每个前缀本身 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];
}

统计字符串 $s$ 的所有前缀子串在 $t$ 中出现的次数， $m = |s|, n = |t|$ 。拼接字符串 $s$ 和 $t$ ，使得 $S = s + \# + t$ 。

首先统计前缀数组值 $\pi[i](i > m)$ ， $\pi[i]$ 表示字符串 $S[0..i]$ 最长相等真前后缀长度，即说明前缀 $S[0..\pi[i]-1]$ 在 $S[0..i]$ 中出现了 1 次（不包括前缀本身），易知最长真前后缀都不会包含界定符 $\#$ ，故统计得到的只是字符串 $t$ 中的。

前缀数组值统计后，只统计出了每个前缀作为某个字符串 $S[0..i]$ 的最长真后缀的出现次数，而没有统计非最长真后缀的出现次数，故根据 $\pi$ 数组的性质统计非最长真后缀的出现次数。

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 不同子串数目

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

设字符串 $s[0..i]$ 的不同子串数目为 $k$ ，则向 $s[0..i]$ 末尾添加一个字符后得到字符串 $s[0..i+1]$ 。显然 $s[0..i+1]$ 的子串中可能会出现一些新的以 $s[i+1]$ 结尾的子串。
反转字符串 $s[0..i+1]$ 得到字符串 $t$ ，则问题变成统计以 $s[i+1]$ 开头且未在 $t$ 的其他地方出现的前缀数目。
设 $t$ 的前缀函数的最大值为 $\pi_{max}$ ，则最长的出现在 $t$ 其他地方的前缀长度为 $\pi_{max}$ ，故更短的前缀也一定出现了。
因此，字符串 $s$ 新增一个末尾字符 $s[i+1]$ 后新出现的子串的数目为 $|s| + 1 - \pi_{max}$ 。

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

4.5 字符串压缩

给定字符串 $s$ ，其长度 $|s| = n$ ，我们希望找到一个最短的字符串 $t$ ，使得 $s$ 为 $t$ 的一份或多份拷贝的拼接表示。
显然，我们只需要找到 $t$ 的长度即可，该问题的答案即为长度为该值的 $s$ 的前缀。

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

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;
    }
};