题解：P3375 【模板】KMP

changxiang2012 · 2025-05-18 15:18:47 · 题解

KMP 算法模板题解：字符串匹配与 Border 计算

KMP 算法是处理字符串匹配问题的经典算法，本题要求实现 KMP 算法的两个核心功能：子串匹配和前缀函数（ border 数组）计算。

问题分析

题目要求解决两个问题：

1. 找出字符串 s2 在 s1 中所有出现的位置。
2. 计算 s2 每个前缀的最长 border 长度。

这里的 border 定义为：既是字符串前缀又是后缀的非本身最长子串。例如，字符串 "ABA" 的最长 border 是 "A" ，长度为 1。

KMP 算法核心思想

KMP 算法的核心在于利用已经匹配过的信息，避免在匹配失败时从头开始。这通过构建一个前缀函数（next 数组）来实现，该数组记录了每个前缀的最长 border 长度。

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <cctype>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <ctime>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <time.h>
#include <random>//poj*
#include <chrono>//poj*
#include <unistd.h>//poj*
#define int long long
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e6+5;
using namespace std;
int n,m;
int nxt[N];
char A[N];
char B[N];
void Prepare(){
    nxt[1] = 0;
    int cur = 0;
    for(int i = 2;i <= n;i++){
        while(cur && A[cur + 1] != A[i]){
            cur = nxt[cur];
        }
        if(A[cur + 1] == A[i]) nxt[i] = ++cur;
        else nxt[i] = 0;
    }
} 
void mate(){
    int cur = 0;
    for(int i = 1;i <= m;i++){
        while(cur > 0 && A[cur + 1] != B[i]){
            cur = nxt[cur];
        }
        if(A[cur + 1] == B[i]) cur++;
        if(cur == n) cout<<i - n + 1<<endl;
    }   
}
signed main(){
    cin.tie(nullptr);
    cout.tie(nullptr);
    scanf("%s%s",B + 1,A + 1);
    n = strlen(A + 1);
    m = strlen(B + 1);
    Prepare();
    mate();
    for(int i = 1;i <= n;i++){
        cout<<nxt[i]<<" ";
    }
    return 0;
}
/*
*注释&笔记:无
*样例输入:

*样例输出:

*/

前缀函数（ next 数组）计算

前缀函数计算的核心是 Prepare 函数，它构建了 next 数组：

• 计算过程中，利用已经计算出的前缀函数值来加速后续计算。
• 时间复杂度为 O(n)，其中 n 是模式串长度。

字符串匹配过程

字符串匹配由 mate 函数完成：

• 使用预处理得到的 next 数组，在匹配失败时跳过不必要的比较。
• 时间复杂度为 O(m)，其中 m 是文本串长度。

复杂度分析

• 预处理时间复杂度：O(n)。
• 匹配时间复杂度：O(m)。
• 总时间复杂度：O(n + m)。
• 空间复杂度：O(n)，主要用于存储 next 数组。

示例解释

对于样例输入：

ABABABC
ABA

模式串 "ABA" 的 next 数组为： [0, 0, 1]。

• 前缀 "A" 的最长 border 长度为 0。
• 前缀 "AB" 的最长 border 长度为 0。
• 前缀 "ABA" 的最长 border 长度为 1（即 "A" ）。

模式串在文本串中出现的位置为 1 和 3，对应输出的前两行。

感谢@whoseJam的讲解