12/1~12/7 kmp算法介绍
2025-12-08 21:37:10
发布于：上海
12/1 - 12/7
废话
我想看小潭山。但我没时间。好气。
”你去年冬天指给我看的那只蝴蝶，早就已经就死在雪里了。“————今天歇
“一个人能能走的多远不在于TA在顺境时能走的多快，而在于TA在逆境时多久能找到曾经的自己。
————KMP”——————小鱼在家_
——————————————————————————————————————————
本周学习了很多东西啊。
包括了：
1.部分数学
2.kmp
3.剪枝DFS
总感觉太仓促了。
主要讲kmp和DFS吧。数学学的也不多。
先看这个：链接描述
这个是kmp的模板（？
下面对这题的讲解基于对链接描述的理解
先放个代码吧：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int nxt[N];
int main(){
string s1,s2;
cin>>s1>>s2;
int i=1;
int len=0;
while(i<s2.size()){
if(s2[i]==s2[len]){
len++;
nxt[i]=len;
i++;
}else{
if(len==0)i++;
else len=nxt[len-1];
}
}
i=0;
int j=0;
while(i<s1.size()){
if(s1[i]==s2[j]){
i++;
j++;
}else{
if(j==0)i++;
else j=nxt[j-1];
}
if(j==s2.size())cout<<i-j+1<<endl;
}
for(int i=0;i<s2.size();i++)cout<<nxt[i]<<" ";
return 0;
}
首先，明确好kmp算法的作用。
给出两个字符串s1,s2。
想要求取s2在s1中是否出现，出现的次数，出现的位置。
这就是kmp算法的作用。
但仅仅只是解决问题不能体现kmp的魅力所在，
重要的是，它是如何快速，优雅的实现的。
明确：你想要实现，暴力轻松打出。
那么n=1e6怎么办？
发现整个算法分为明确的两部分：
求取nxt数组，在s1中寻找s2的踪迹。
好的，nxt数组是什么？
nxt[i]表示：s2这个字符串，从0到i截取，其最长公共前后缀的长度。
明确“公共前后缀”的定义：
比如"baba"，其公共前后缀为"ba"。
再比如"babab"，其公共前后缀为bab.
明确定义，开始细纠代码：
int i=1;
int len=0;
while(i<s2.size()){
if(s2[i]==s2[len]){
len++;
nxt[i]=len;
i++;
}else{
if(len==0)i++;
else len=nxt[len-1];
}
}
- kmp算法每一行都需要细究
首先，这里我的代码中，string从零开始，注意个人习惯，记得辨别区分。
i=1
len=0
i和len的定义：在s2这个字符串中，前i个字符的最长公共前后缀为len。
所以说，i肯定是比len大的。
因为nxt数组是在s2里操作的，所以"i<s2.size()".
判断，
如果s2[i]与s2[len]字符相同，
len++（注意，len一开始的初始值为0，所以要先加
nxt[i]=len（i没有加，因为i一开始就是1，如果说两个字符相同，len加好后就吧nxt[i]赋值掉）
i++（然后i再加，i是“提前先走的”）
如果不相同。
那么再次进行判断：
判断len是否为零。
如果len不为零：len=nxt[len-1];
这一句有点抽象。
结合例子进行理解：
ABABABC
比如说现在：
最长公共前后缀是“ABAB”
然后就要判断：
ABABABC
“A”和“C”这两个加粗的字母是否相同。
检测到它们是不同的，那么len=3 -> len=1
为什么能这么做？
须知，在s2的0-len-1中，0 ~ nxt[len-1]和 len-1-nxt[len-1] ~ len-1是相同的。
现在又知道：len-1-nxt[len-1] ~ len-1 和 i-1-nxt[i-1] ~ i-1 是相同的。
那么 0 ~ nxt[len-1] 和 i-1-nxt[i-1] ~ i-1是相同的。
既然这两段是相同的，那就可以继续去判断nxt[len-1]+1和i是否是相同的。
至于len是零，那也退无可退，直接让i往后走一格就好了。
找公共前后缀时，发现有不符合条件的，不一定一定要从头开始找，而是利用过去的信息，巧妙减少时间。
那么，补充nxt的部分告一段落，接下来就是在s1中寻找s2出现的位置。
i=0;
int j=0;
while(i<s1.size()){
if(s1[i]==s2[j]){
i++;
j++;
}else{
if(j==0)i++;
else j=nxt[j-1];
}
if(j==s2.size())cout<<i-j+1<<endl;
}
注意到，i变回了0，新增变量j=0。
i和j分别是字符串s1和s2中的指针。
因为j不断在0 ~ s2.size() 之间游走，所以它时不算数的。
判断终止条件，判断的就是i。
如果说，s1[i]和s2[j]相同。
那么让它们都分别往后移一格。
如果不相同，判断j是否等于零。
逻辑根刚刚还挺像的吧。不多说。
后面补了一句，问j是否等于s2.size()
注意，不是s2.size()-1，因为如果"s1[i]==s2[j]" 那么 " j++"。
结束。
这里空空如也
有帮助，赞一个