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

import java.io.*;
import java.util.*;

public class Main {
     public static void main(String[] args) throws IOException {
        // 创建缓冲读取器，用于从标准输入读取数据
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 创建打印输出器，用于向标准输出打印数据
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        // 读取测试用例的数量T
        int T = Integer.parseInt(br.readLine().trim());

        // 处理每个测试用例
        while (T-- > 0) {
            // 读取一行输入并分割成字符串数组
            String[] s = br.readLine().trim().split("\\s+");
            // 获取字符串的长度n
            int n = Integer.parseInt(s[0]);

            // 计算前缀函数数组
            int[] pi = computePre(s[1], n);

            // 输出前缀函数数组，元素间用空格分隔
            for (int i = 0; i < n; i++) {
                out.print(pi[i] + (i == n - 1 ? "" : " "));
            }
            // 换行
            out.println();
        }

        // 刷新输出缓冲区，确保所有输出都被写出
        out.flush();
        // 关闭输出流
        out.close();
        // 关闭输入流
        br.close();
    }

    /**
     * 计算字符串的前缀函数（Prefix Function）
     * 前缀函数pi[i]表示字符串s[0..i]的最长相等前后缀的长度（不包括s[0..i]本身）
     *
     * @param s 输入的字符串
     * @param n 字符串的长度
     * @return 返回前缀函数数组pi，其中pi[i]表示s[0..i]的最长相等前后缀长度
     */
    private static int[] computePre(String s, int n) {
        int[] pi = new int[n];  // 初始化前缀函数数组，长度为n

        // 从第二个字符开始遍历字符串
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];  // 初始化j为前一个字符的前缀函数值

            // 当j大于0且当前字符不匹配时，通过前缀函数回退
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = pi[j - 1];  // 回退到前一个可能匹配的位置
            }

            // 如果当前字符匹配，则增加匹配长度
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }

            // 将当前字符的前缀函数值存入数组
            pi[i] = j;
        }
        return pi;  // 返回计算得到的前缀函数数组
    }
}