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

题目链接

【模板】前缀函数（kmp）

题目描述

给定字符串 $s$ 的多个查询。对每个查询字符串（长度为 $n$ ），定义其前缀函数 $\pi$ ： $\pi_i$ 为 $s[1..i]$ 的最长相等真前缀与真后缀的长度（可为 $0$ ）。你需要输出整串的前缀函数： $\pi_1,\pi_2,\ldots,\pi_n$ 。

解题思路

记 $\pi_1=0$ 。对 $i=2\ldots n$ ，令 $j=\pi_{i-1}$ ，不断回退 $j\leftarrow\pi_j$ 直到 $j=0$ 或 $s[i]=s[j+1]$ 。
若匹配则 $j\leftarrow j+1$ ，令 $\pi_i\leftarrow j$ 。该算法按字符线性推进，每个位置的指针最多回退若干次，总体 $\mathcal{O}(n)$ 。
多组数据独立处理，保证所有 $n$ 之和约束内可在线性时间完成。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; if (!(cin >> T)) return 0;
    while (T--) {
        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) {
            if (i) cout << ' ';
            cout << pi[i];
        }
        cout << '\n';
    }
    return 0;
}

import java.util.*;

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];
            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;
            }
            StringBuilder out = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if (i > 0) out.append(' ');
                out.append(pi[i]);
            }
            System.out.println(out.toString());
        }
    }
}

T = int(input())
for _ in range(T):
    parts = input().split()
    if len(parts) == 1:
        n = int(parts[0])
        s = input().strip()
    else:
        n = int(parts[0])
        s = parts[1]
    pi = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    print(' '.join(str(x) for x in pi))

算法及复杂度

算法：线性前缀函数（KMP 前缀表）迭代构造。
时间复杂度：单组 $\mathcal{O}(n)$ ，多组总计 $\mathcal{O}(\sum n)$ 。
空间复杂度： $\mathcal{O}(n)$ 。