专栏文章

题解：P3375 【模板】KMP （显眼包）

cchu_yh
P3375题解参与者 10已保存评论 11

文章操作

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

当前评论
11 条
当前快照
1 份
快照标识符
@mipr7z9h
此快照首次捕获于
2025/12/03 16:37
3 个月前
此快照最后确认于
2025/12/03 16:37
3 个月前
查看原文
Update on 2025/7/28：将讨论区里提出的常见问题做出解答，应用新版格式，并删除开头废话。麻烦管理员通过。
如有问题欢迎在讨论区提出！

用途

在字符串初级算法里，而其中最经典的模型问题就是判断一个串是否是另一个串的子串。我们常用 KMP 算法解决这类问题。

题目描述

给定两个字符串 s1s_1 和 s2s_2，求出 s2s_2 在 s1s_1 中所有出现的位置和 s2s_2 的每个前缀 s′s' 的最长 border 的长度。
在本题解中，我用 nn 代替 ∣s1∣|s_1|（即 s1s_1 的长度），用 mm 代替 ∣s2∣|s_2|。

暴力匹配

枚举 s1s_1 的每一个起始位置 i(0≤i<n−m)i(0\le i<n-m)，看从 ii 位置开始往后长度为 mm 的子串是否是可以和 s2s_2 匹配。
判断两个串匹配成功的条件是：两个串长度一致，两个串每一个对应位置字符都完全一样。
本做法时间复杂度为 O(nm)O(nm)，只能得 70 分，比总司令高。

更优做法：KMP

定义

定义一个字符串性质——前缀后缀最大值，即题目中要求的 border（让你求那多半要用）。
定义一个字符串 ss 的 border 为 ss 的一个非 ss 本身的子串 tt，满足 tt 既是 ss 的前缀，又是 ss 的后缀。
我将字符串 ss 的前缀 s′s' 的最长 border 的长度称为 next∣s′∣next_{|s'|}，别问我为啥。
换句话说，nextinext_i 就是遍历到字符串 s2s_2 的第 ii 位时，与已经匹配成功的部分的后缀相同的最大的长度。我代码中的 kmp[i] 就是 nextinext_i。

匹配过程

举例说明，其中 s1s_1 为 ABACABACABD，s2s_2 为 ABACABD。
先将 s1s_1 和 s2s_2 的第一位对齐并看对应位是否相同，我们发现一路畅通，但最后一个匹配失败了。若这时对齐 s1s_1 的第二位和 s2s_2 的第一位将 s2s_2 重新匹配一遍就成了暴力。
CPP
      i
ABACABACABD
ABACABD
      j
仔细回想 nextnext 定义发现：失配后，我们可以直接跳到 nextjnext_j，即与已匹配部分相同的 s2s_2 最大前缀的最后一位的下一位，手动得出此时 nextj=2next_j=2。然后就会变成这样：
CPP
      i
ABACABACABD
    ABACABD
      j
这样做，复杂度为 O(n+m)O(n+m)。

求 nextnext

将 s2s_2 自己和自己匹配，过程和上面相仿。匹配到 jj 失败时，记录 nextinext_i 为 jj。匹配时一个字符串不动，另一个向后移，ii 为匹配到不动的 s2s_2 的位置，jj 为匹配到要动的 s2s_2 的位置。
具体实现见代码。

实现

代码CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+2;
int kmp[N],la,lb,j;
//kmp即Next数组,表示相同前缀后缀最大值(不是对称的最大值)
string a,b,A,B;

int main(){
	cin>>A>>B;
	a='\0'+A,b='\0'+B;
	la=a.size()-1,lb=b.size()-1;
	for(int i=2;i<=lb;i++){//求kmp
		while(j&&b[i]!=b[j+1]) j=kmp[j];
		if(b[j+1]==b[i]) j++;
		kmp[i]=j;
	}
	j=0;
	for(int i=1;i<=la;i++){//匹配
		while(j>0&&b[j+1]!=a[i]) j=kmp[j];
		if(b[j+1]==a[i]) j++;
		if(j==lb){printf("%d\n",i-lb+1);j=kmp[j];}
	}
	for(int i=1;i<=lb;i++) printf("%d ",kmp[i]);
	return 0;
}
讨论区常见问题

问题

为什么求 kmp 数组（代码第 12 行）下标 ii 要从 22 开始到 b.size()-1 结束啊？

回答

首先 ii 以 b.size()-1 结束并不难理解，我加了个空字符 \0 来让字符串下标从 11 开始，但我用 b.size() 求出的大小会把 \0 算上，因此要减一。
然后回答为什么 ii 要从 22 开始。先理解 kmp 数组的定义和作用，然后再手动推一下发现如果从 11 开始 kmp[1] 就会变为 11 而非 00 导致后面模式串与文本串比对时在 11 这个位置回跳时不断往下标为 11 的位置跳而死循环。
点个赞再走呗。

评论

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

正在加载评论...