1. 定义

1.1 前缀 & 真前缀

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

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

真前缀指除了 $S$ 本身的 $S$ 的前缀。

1.2 后缀 & 真后缀

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

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

真后缀指除了 $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$ 为最大的相等的真前后缀长度，即

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

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

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

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$，则：

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

3. 实现

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

• $s[0] = 0$ 。

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

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

• 如果 $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]$ 为止，则

$$\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 算法，思路为：拼接模式串 $s$ 和主串 $t$，得到 $S = s + \# + t$，$\#$ 为不在 $s$ 和 $t$ 中出现的字符。设

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

计算拼接后的字符串 $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|$。

1. 首先统计前缀数组值 $\pi[i]$，$\pi[i]$ 表示字符串 $s[0..i]$ 最长相等真前后缀长度，即说明前缀 $s[0..\pi[i]-1]$ 在 $s[0..i]$ 中出现了 1 次（不包括前缀本身）。
2. 前缀数组值统计后，只统计出了每个前缀作为某个字符串 $s[0..i]$ 的最长真后缀的出现次数，而没有统计非最长真后缀的出现次数，故根据 $\pi$ 数组的性质统计非最长真后缀的出现次数。
3. 加上每个前缀本身 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$ 。

1. 首先统计前缀数组值 $\pi[i], i \gt m$，$\pi[i]$ 表示字符串 $S[0..i]$ 最长相等真前后缀长度，即说明前缀 $S[0..\pi[i]-1]$ 在 $S[0..i]$ 中出现了 1 次（不包括前缀本身），易知最长真前后缀都不会包含界定符 $\#$，故统计得到的只是字符串 $t$ 中的。
2. 前缀数组值统计后，只统计出了每个前缀作为某个字符串 $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;

#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