前缀函数题型整理

前缀函数相关内容详见 前缀函数理论，本文展开讲解 $\pi$ 数组的一百种应用。

Border 与 周期

问题

P4391 Radio Transmission 无线传输
给定一个字符串 $S_1$，它是某个字符串 $S_2$ 不断自我连接后得到的一个前缀，求 $S_2$ 的最短可能长度。

数据规模：$N \le 10^6$。

如果一个字符串 $S_{1}$ 是由 $S_{2}$ 重复拼接后得到的前缀，那么 $S_{1}$ 一定具有周期性。

由 前缀函数理论 可知，对于一个长度为 $L$ 的字符串，如果它有一个长度为 $x$ 的 Border，那么 $L - x$ 就是该字符串的一个周期。

本题要求最短周期，等价于求最长的 Border，于是答案就是 $n - \pi[n-1]$。

沿 Border 链的问题

问题

P3435 OKR-Periods of Words
如果 $Q$ 是 $A$ 的真前缀，并且 $A$ 是 $QQ$ 的前缀，则称 $Q$ 是 $A$ 的周期。求字符串所有前缀的最大周期长度之和。

数据规模：$N \le 10^6$。

本题要求所有前缀的最大周期长度之和。同上，最长周期等价于最短 Border，同时要求 Border 是非空的。

于是我们可以沿着 Border 链往上找到最后一个 $> 0$ 的长度，当然直接对每个前缀都跑一遍，复杂度显然是 $\mathcal{O}(n^{2})$ 的，这是不可接受的。

所以我们考虑优化，记录重复查询的位置，定义 border[len]表示长度为 len 的前缀的最短非空 Border 长度。

设 $b = \pi[len-1]$，若 $b = 0$，说明当前前缀没有非空 Border，若 $b \neq 0$，则说明长度为 b 的前缀还有更短的非空 Border，直接继承答案即可，否则，b本身就是最短非空 Border。

▶

P3435

void build( const string &s ) { /* 模板代码略 */ }
int border[maxn];

void solve( ) {
    int n = read( );
    string S;
    cin >> S;
    build( S );
    
    ll ans = 0;
    for( int i = 1; i <= n; ++ i ) {
        int j = pi[i - 1];
        if( j == 0 ) {
            border[i] = 0;
            continue;
        }
        if( border[j] ) border[i] = border[j];
        else border[i] = j;
        ans += i - border[i];
    }
    cout << ans << '\n';
}

---

问题

P2375 动物园
对字符串的每个前缀，统计既是它的前缀又是它的后缀，并且前后两段不重叠的字符串数量。最后输出所有数量加一后的乘积。

数据规模：字符串总长度不超过 $10^6$。

对于长度为 len 的前缀，它的所有 Border 都位于失配树上从节点 len到根节点的路径中。

先不考虑 “不重叠” 的限制，定义 dep[len] 为节点 len在失配树上的深度。

由于长度为 len的前缀的父亲是 pi[len-1]，所以 dep[len] = dep[pi[len-1]] + 1。

如果找到一个合法的 Border 长度 $j$，那么 dep[j] 就表示从 $j$ 开始沿 Border 链能够得到的非空 Border 数量。

接着考虑 “不重叠” 的限制，发现长度为 $j$ 的前缀和后缀不重叠，当且仅当 $2j \le len$。

所以沿着 Border 链往回跳，找到满足条件的 $j$ 就行了，注意还有不选择的情况，所以乘法因子还要 $+1$。

▶

P2375

void build( const string &s ) { /* 模板代码略 */ }
int dep[maxn];

void solve( ) {
    string S;
    cin >> S;
    build( S );

    int n = S.length( );
    ll ans = 1;

    for( int len = 1; len <= n; ++ len ) {
        dep[len] = dep[ pi[len-1] ] + 1;
    }

    for( int i = 1, j = 0; i < n; ++ i ) {
        while( j && S[i] != S[j] ) j = pi[j - 1];
        if( S[i] == S[j] ) ++ j;
        while( j * 2 > i + 1 ) j = pi[j - 1];
        ans = ( ans * (dep[j] + 1) ) % mod;
    }
    cout << ans << '\n';
}

前缀函数信息不够

问题

P3426 SZA-Template
给定字符串 $S$，求最短字符串 $T$，使得可以通过若干次允许重叠的盖印，用 $T$ 覆盖整个字符串。

数据规模：$N \le 5 \times 10^5$。

朴素的想法是对每个子串都 Check 一下，发现复杂度约为 $\mathcal{O}(n^{3})$，因为子串 $\mathcal{O}(n^{2})$，每一个 Check 复杂度是 $\mathcal{O}(n)$。

不难注意到，一个能够覆盖整个字符串的印章 $T$，必须覆盖原串的开头和结尾。所以，如果 $T$ 比原串短，那么它一定是原串的一个 Border。

于是，可以沿着 Border 链枚举所有可能的印章。一个字符串最多有 $\mathcal O(n)$ 个 Border，如果对每个候选印章都进行一次 $\mathcal O(n)$ 的检查，总复杂度仍然是 $\mathcal O(n^2)$，还需要继续优化。

设印章长度为 $k$，它在原串中出现位置依次为：$p_1 < p_2 < \cdots < p_t$，为了覆盖原串的开头结尾，必须满足 $p_{1} = 0, p_{t} = n - k$。

同时，两个相邻的起点距离不能超过 $k$，因此 $p_{i+1} - p_{i} \le k$。也就是说，判断一个长度为 $k$ 的 Border 是否合法，只需要检查它的相邻出现位置之间是否存在超过 $k$ 的空缺。

所以我们可以直接对每个 Border 求出所有出现位置，然后依次判断，发现仍然会处理大量重复信息，所以我们考虑用 DP 来转移前缀信息。

定义 $f[len]$ 表示覆盖长度为 $len$ 的前缀所需的最短印章长度。

由于整个前缀本身一定可以作为印章，所以初始有 $f[len] = len$。记 $b = \pi[len - 1]$，若长度 $len$ 的前缀存在一个更短的合法印章，那么它一定能够覆盖长度为 $b$ 的最长 Border。

所以当前前缀 $len$ 的最优答案只能是 $f[len] = \{ len, f[b] \}$，于是我们考虑如何判断长度为 $f[b]$ 的印章是否能覆盖当前前缀。

这里开个数组记录一下就行，记 $lst[k]$ 表示此前能够用长度为 $k$ 的印章完整覆盖的最长前缀长度。同样，后缀 $[len - b, len)$ 这一段也可以用相同的方式覆盖。

我们只需要判断，前面使用该印章覆盖到的位置不早于这个后缀的起点即可：$lst[f[b]] \ge len - b$。若满足条件，则可以完整衔接，也就可以转移。

▶

P3426

void build( const string &s ) { /* 模板代码略 */ }
int f[maxn];
int lst[maxn];

void solve( ) {
    string S;
    cin >> S;
    build( S );

    int n = S.length( );

    f[0] = 0;
    for( int len = 1; len <= n; ++ len ) {
        f[len] = len;
        int border = pi[len - 1];
        if( border ) {
            int k = f[border];
            if( lst[k] >= len - border ) f[len] = k;
        }
        lst[ f[len] ] = len;
    }
    cout << f[n] << '\n';
}

匹配的同时删除

问题

P4824 Censoring S
给定文本串 $S$ 和模式串 $T$。从左向右处理 $S$，每当当前字符串结尾出现一次 $T$，就立刻删除它，求最终字符串。

数据规模：字符串长度不超过 $10^6$。

如果只是匹配，可以用标准的 KMP 来实现，但本题会删除已经处理过的字符，删除以后，新的字符串结尾可能与更早的字符重新连接，当前匹配状态 $j$ 不能简单按照 KMP 继续了。

这里会想到一种做法：每一轮用 KMP 找出当前字符串中所有互不重叠的 $T$，将它们统一删除，然后对得到的新字符串重新匹配。

但这种做法不具备正确性。题目要求每次删除当前字符串中最靠前的 $T$；删除前面的匹配后，断点两侧的字符会重新连接，可能产生一个新的、更靠前的匹配。这个新匹配甚至可能与本轮中尚未删除的某个旧匹配共享字符，因此后面的旧匹配不一定还能被删除。

比如 aabababa | aba 它们会得到不同的结果 a[aba]b[aba] 以及 [a[aba]ba]ba。这个现象本质上与删除后保留下来的 KMP 匹配状态有关。删除一段匹配以后，左侧字符串的结尾可能已经匹配了模式串的某个前缀，继续读入右侧字符后，就可能跨过删除位置形成新的 $T$。

所以需要换一种顺序来解决问题，这里采用栈来维护当前仍然保留的字符，对于栈中的每个位置，再记录加入该字符后对应的 KMP 匹配长度，当 $j = m$ 时，说明栈顶出现了一个完整的 $T$，直接弹出最后 $m$ 个字符。

▶

P4824

int pi[maxn];
void build( const string &s ) { /* 模板代码略 */ }

char stk[maxn];
int f[maxn];

void solve( ) {
    string S, T;
    cin >> T >> S;
    build( S );

    int n = T.length( ), m = S.length( );
    int top = 0;
    
    for( int i = 0, j = 0; i < n; ++ i ) {
        while( j && T[i] != S[j] ) j = pi[j - 1];
        if( T[i] == S[j] ) ++ j;
        stk[++ top] = T[i];
        f[top] = j;
        if( j == m ) {
            top -= m;
            j = f[top];
        }
    }

    for( int i = 1; i <= top; ++ i ) cout << stk[i];
}

匹配与自动机

问题

P3193 [HNOI2008] GT考试
构造一个长度为 $N$ 的数字串，要求其中不出现给定的长度为 $M$ 的不吉利数字串，求合法数字串数量对 $K$ 取模的结果。数字串允许以 $0$ 开头。

数据规模：$N \le 10^9$，$M \le 20$，$K \le 10^4$。

由于这是一个计数问题，可以尝试使用 DP。

定义 $f[i][j]$ 表示已经构造了长度为 $i$ 的数字串，当前字符串后缀与模式串前缀的最大匹配长度为 $j$，并且此前没有完整出现过模式串的方案数。

其中 $0 \le j < M$，状态 $j = M$ 表示已经完整匹配模式串，即数字串中出现了不吉利数字，属于非法状态，无法转移。

接着枚举新加入的数字字符 ch，对于当前状态 $j$ 来说，加入一个字符后的转移过程，本质就是一次 KMP 匹配，为了方便 DP 的状态转移，我们考虑对原串建立前缀自动机。

记 $go[j][d] = k$ 表示当前与模式串前缀匹配了 $j$ 个字符，再加入数字 $d$ 后，新的最大匹配长度为 $k$。

有了自动机，就可以进行线性 DP了：

▶

自动机

for( int i = 0; i < N; ++ i ) {
    for( int j = 0; j < M; ++ j ) {
        for( int d = 0; d <= 9; ++ d ) {
            int k = go[j][d];
            if( k < M ) f[i + 1][k] += f[i][j];
        }
    }
}

发现 $N = 1e9$，所以我们还需要一点线代的智慧，用矩阵快速幂来加速递推。

定义 $mat[i][j]$ 表示从状态 $i$ 加入一位数字后，有多少种数字转移到状态 $j$。

它可以通过前缀自动机快速构建：

▶

转移矩阵

for( int i = 0; i < M; ++ i ) {
    for( int d = 0; d <= 9; ++ d ) {
        int j = go[i][d];
        if( j < M ) ++ mat[i][j];
    }
}

于是就可以愉快的线性递推答案了，$\displaystyle f[i][j] = \sum_{k=0}^{m-1} mat[k][j] \cdot f[i-1][k]$，这个 $mat$ 矩阵就可以通过 $go$ 自动机来快速构建。

将第 $i$ 层 DP 写成列向量 $F_{i}$，则有 $F_{i} = mat \cdot F_{i-1}$，初始时还没加入任何字符，此时只有状态 $0$ 存在一种方案：

$$F_{0} = \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}$$

最终答案是所有合法状态的方案数之和：$\displaystyle \sum_{j=0}^{m-1}F_N[j]$

▶

P3193

int mod;

struct Matrix { /* 模板代码略 */ };
Matrix mqpow( Matrix a, ll k ) { /* 模板代码略 */ }

int pi[maxn];
void build( const string &s ) { /* 模板代码略 */ }

int go[maxn][10];
Matrix build2( string s ) {
    int m = (int)s.size( );
    for( int j = 0; j < m; ++ j ) {
        for( int d = 0; d <= 9; ++ d ) {
            char ch = d + '0';
            int k = j;
            while( k && ch != s[k] ) k = pi[k - 1];
            if( ch == s[k] ) ++ k;
            go[j][d] = k;
        }
    }
    Matrix mat( m );
    for( int i = 0; i < m; ++ i ) {
        for( int d = 0; d <= 9; ++ d ) {
            int j = go[i][d];
            if( j < m ) mat.m[j+1][i+1] ++;
        }
    }
    return mat;
}

void solve( ) {
    int n = read( ), m = read( );
    mod = read( );
    string s;
    cin >> s;
    build( s );
    Matrix mat = build2( s );
    mat = mqpow( mat, n );
    ll ans = 0;
    for( int j = 0; j < m; ++ j ) {
        ans = ( ans + mat.m[j+1][1] ) % mod;
    }
    printf( "%lld\n", ans );
}

小结

KMP 其实很少单独在题目中考察，更本质的其实是前缀函数 $\pi$ 的性质与应用。