专栏文章

题解：P3375 【模板】KMP

cchangxiang2012
P3375题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip9oqo2
此快照首次捕获于
2025/12/03 08:26
3 个月前
此快照最后确认于
2025/12/03 08:26
3 个月前
查看原文

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

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

问题分析

题目要求解决两个问题：
  1. 找出字符串 s2s2 在 s1s1 中所有出现的位置。
  2. 计算 s2s2 每个前缀的最长 border 长度。
这里的 border 定义为：既是字符串前缀又是后缀的非本身最长子串。例如，字符串 "ABA" 的最长 border 是 "A" ，长度为 11。

KMP 算法核心思想

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

AC代码

CPP
#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 数组）计算

前缀函数计算的核心是 PreparePrepare 函数，它构建了 nextnext 数组：
  • next[i]next[i] 表示模式串 AA 的前 ii 个字符组成的前缀的最长 border 长度。
  • 计算过程中，利用已经计算出的前缀函数值来加速后续计算。
  • 时间复杂度为 O(n)O(n)，其中 nn 是模式串长度。

字符串匹配过程

字符串匹配由 matemate 函数完成：
  • 使用预处理得到的 nextnext 数组，在匹配失败时跳过不必要的比较。
  • 时间复杂度为 O(m)O(m)，其中 mm 是文本串长度。

复杂度分析

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

示例解释

对于样例输入：
CPP
ABABABC
ABA
模式串 "ABA" 的 nextnext 数组为： [0,0,1][0, 0, 1]。
  • 前缀 "A" 的最长 border 长度为 00。
  • 前缀 "AB" 的最长 border 长度为 00。
  • 前缀 "ABA" 的最长 border 长度为 11（即 "A" ）。
模式串在文本串中出现的位置为 11 和 33，对应输出的前两行。
感谢@whoseJam的讲解

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...