前缀函数

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