algorithm-string-kmp

KMP算法概念

KMP算法是一种用于字符串匹配的经典算法，它的全名是Knuth-Morris-Pratt算法，是由Donald Knuth、Vaughan Pratt和James H. Morris分别独立发明的。KMP算法用于在一个主文本字符串中查找一个模式字符串的出现，它的主要优势在于在匹配失败时避免不必要的回溯。

KMP算法通过构建部分匹配表（Partial Match Table），也称为最长前缀后缀匹配表（Longest Prefix Suffix Table），来避免这种不必要的比较。

性能分析

KMP算法的时间复杂度为O(m + n)，其中m是主文本字符串的长度，n是模式字符串的长度。

参考

算法学习笔记(13): KMP算法

模板

// 利用匹配获取pmt数组
public static int[] getPmt(char[] pattern) {
    int pmt[] = new int[pattern.length];  // pmt[0] = 0;
    // 计算pmt，在错开一位后，让p自己匹配自己（这相当于是用前缀去匹配后缀）
    for (int i = 1, j = 0; i < pattern.length; i++) {
        while (j != 0 && pattern[i] != pattern[j]) j = pmt[j - 1];
        if (pattern[i] == pattern[j]) j++;
        pmt[i] = j;
    }
    return pmt;
}

// 计算匹配次数
public static int count(char[] s, char[] p, int[] pmt) {
    int res = 0;
    for (int i = 0, j = 0; i < s.length; i++) {
        while (j != 0 && s[i] != p[j]) j = pmt[j - 1];
        if (s[i] == p[j]) j++;
        if (j == p.length) {
            res += 1;
            // System.out.println(i - j + 2);  // 输出位置（从1开始数）
            j = pmt[j - 1];
        }
    }
    return res;
}

P3375 【模板】KMP

题目描述

给出两个字符串 $s_1$ 和 $s_2$ ，若 $s_1$ 的区间 $[l, r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$ 。
现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。

定义一个字符串 $s$ 的 border 为 $s$ 的一个非 $s$ 本身的子串 $t$ ，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。
对于 $s_2$ ，你还需要求出对于其每个前缀 $s'$ 的最长 border $t'$ 的长度。

输入格式

第一行为一个字符串，即为 $s_1$ 。
第二行为一个字符串，即为 $s_2$ 。

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 $s_2$ 在 $s_1$ 中出现的位置。
最后一行输出 $|s_2|$ 个整数，第 $i$ 个整数表示 $s_2$ 的长度为 $i$ 的前缀的最长 border 长度。

样例 #1

样例输入 #1

1 2	ABABABC ABA

样例输出 #1

1
2
3

1
3
0 0 1

提示

样例 1 解释

。

对于 $s_2$ 长度为 $3$ 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 $1$ 。

数据规模与约定

本题采用多测试点捆绑测试，共有 3 个子任务。

Subtask 1（30 points）： $|s_1| \leq 15$ ， $|s_2| \leq 5$ 。
Subtask 2（40 points）： $|s_1| \leq 10^4$ ， $|s_2| \leq 10^2$ 。
Subtask 3（30 points）：无特殊约定。

对于全部的测试点，保证 $1 \leq |s_1|,|s_2| \leq 10^6$ ， $s_1, s_2$ 中均只含大写英文字母。

KMP算法

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int[] getPmt(char[] pattern) {
        int pmt[] = new int[pattern.length];  // pmt[0] = 0;
        // 计算pmt，在错开一位后，让p自己匹配自己（这相当于是用前缀去匹配后缀）
        for (int i = 1, j = 0; i < pattern.length; i++) {
            while (j != 0 && pattern[i] != pattern[j]) j = pmt[j - 1];
            if (pattern[i] == pattern[j]) j++;
            pmt[i] = j;
        }
        return pmt;
    }

    // 计算匹配次数
    public static int count(char[] s, char[] p, int[] pmt) {
        int res = 0;
        for (int i = 0, j = 0; i < s.length; i++) {
            while (j != 0 && s[i] != p[j]) j = pmt[j - 1];
            if (s[i] == p[j]) j++;
            if (j == p.length) {
                res += 1;
                System.out.println(i - j + 2);  // 输出位置（从1开始数）
                j = pmt[j - 1];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            char s[] = in.next().toCharArray(), p[] = in.next().toCharArray();
            int[] pmt = getPmt(p);
            count(s, p, pmt);
            for (int i = 0; i < p.length; i++) {
                System.out.print(pmt[i] + " ");
            }
        }
    }
}