题解 | #【模板】前缀函数（kmp）#

题目链接

题目描述

对于一个长度为 $N$ 的字符串 $S$ ，其前缀函数 $\pi$ 被定义为一个长度为 $N$ 的数组。其中 $\pi[i]$ 的值是字符串 $S$ 的前缀 $S[0...i]$ 的最长真前缀（proper prefix）同时也是其真后缀（proper suffix）的长度。

任务是对于给定的字符串 $S$ ，计算其完整的前缀函数 $\pi$ 数组。

解题思路

这是计算 KMP 算法中 next 数组（或称前缀函数/失配函数）的模板题。该算法使用动态规划的思想，可以在线性时间内完成。

我们用 $\pi[i]$ 表示前缀串 $S[0...i]$ 的最长相等真前缀和真后缀的长度。我们的目标是依次计算出 $\pi[0], \pi[1], ..., \pi[N-1]$ 。

基础情况: 对于 $\pi[0]$ ，由于 $S[0]$ 只有一个字符，没有真前缀或真后缀，所以 $\pi[0]$ 永远为 $0$ 。
递推关系: 假设我们已经计算出了 $\pi[i-1]$ ，现在需要计算 $\pi[i]$ 。设 $j = \pi[i-1]$ 。这个值告诉我们， $S[0...j-1] == S[i-j...i-1]$ 。

我们希望找到一个最长的匹配，对于 $S[0...i]$ 。一个很自然的想法是尝试扩展已有的长度为 $j$ 的匹配。也就是说，我们检查 $S[i]$ 是否等于 $S[j]$ 。
1. 如果 $S[i] == S[j]$ : 这意味着我们可以将长度为 $j$ 的匹配扩展一位，形成一个长度为 $j+1$ 的新匹配。因此， $\pi[i] = j + 1$ 。
2. 如果 $S[i] \neq S[j]$ : 我们无法直接扩展长度为 $j$ 的匹配。我们需要寻找一个更短的、在 $S[0...i-1]$ 中同样满足前缀-后缀相等的长度。下一个最长的可能匹配在哪里呢？它就在长度为 $j$ 的这个前缀 $S[0...j-1]$ 自身的最长相等前后缀中。这个长度就是 $\pi[j-1]$ 。
  
  所以，我们令 $j = \pi[j-1]$ ，然后回到步骤 1，再次比较 $S[i]$ 和新的 $S[j]$ 。我们不断重复这个“失配回溯”的过程，直到 $j$ 变为 $0$ 或者找到一个匹配。
这个过程保证了我们在计算 $\pi[i]$ 时，充分利用了之前计算的结果，避免了不必要的字符比较。通过均摊分析，可以证明整个算法的时间复杂度是线性的。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void solve() {
    int n;
    string s;
    cin >> n >> s;

    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        pi[i] = j;
    }

    for (int i = 0; i < n; i++) {
        cout << pi[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            String s = sc.next();

            int[] pi = new int[n];
            // pi[0] is already 0
            for (int i = 1; i < n; i++) {
                int j = pi[i - 1];
                while (j > 0 && s.charAt(i) != s.charAt(j)) {
                    j = pi[j - 1];
                }
                if (s.charAt(i) == s.charAt(j)) {
                    j++;
                }
                pi[i] = j;
            }

            for (int i = 0; i < n; i++) {
                System.out.print(pi[i] + (i == n - 1 ? "" : " "));
            }
            System.out.println();
        }
    }
}

def solve():
    line = input().split()
    n = int(line[0])
    s = line[1]
    
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
        
    print(*pi)

def main():
    try:
        t = int(input())
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

main()

算法及复杂度

算法：KMP前缀函数计算
时间复杂度： $O(L_{total})$ ，其中 $L_{total}$ 是所有测试用例中字符串长度的总和。
- 外层循环 for (int i = 1; i < n; i++) 执行 $N-1$ 次。在循环体内部，j 的值通过 j++ 最多增加 $N-1$ 次。而 j 的值通过 j = pi[j - 1] 只会减少，且总减少量不会超过总增加量。因此，while 循环的总执行次数是均摊 $O(N)$ 的。
空间复杂度： $O(L_{max})$ ，其中 $L_{max}$ 是单个测试用例中字符串的最大长度，用于存储 $\pi$ 数组。