kmp&字典树 - “今年欢笑复明年“

Baltic 菠萝的海

2026-07-19 19:18:56

发布于：浙江

5阅读

0回复

0点赞

自主学习笔记类产物。不为他人修改。

今年欢笑复明年，秋月春风等闲度。——《琵琶行》

——————————————————————————————————————————

kmp

只要跟前后缀有关的题目基本都能和kmp相关。
然后让我放置一下代码。我需要写一点注释去解释。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int nxt[N];//nxt[i]表示s2这个字符串从0-i这一段子串中长度相等的前后缀 
int main(){
	//输入两字符串 
	string s1,s2;
	cin>>s1>>s2;
	int i=1;//当前我要处理nxt[i] 
	int len=0;//len有很多层含义 
	//1.从0~i-1长度的s2串中相等前后缀长度 
	//2.目前在s2中的某个下标，要去和s2[i]进行匹配判断加不加前后缀 
	//开始处理nxt数组 
	while(i<s2.size()){//i不超过s2.size()
	    //当s2[i]和s2[len]是相等的 
		if(s2[i]==s2[len]){
			//注意这边是++len，因为Len有第二层涵义所以它从0开始
			//但是它又要代表长度所以它代表长度得分时候得加1 
			nxt[i++]=++len;
			// len 当前是前缀长度，也是下一个要比较的下标
			// 因为 s2[i] == s2[len]，说明前后缀可以延长一位
			// 所以新的前缀长度 = len + 1，即 ++len
			//len既代表新长度，也代表新位置。但是新长度是已经确定了的
			//新长度，新位置是下一个要判断的新位置。一个是现在是一个是
			//将来式 
		}else{
			//如果说len已经退无可退了，那么s2[i]本身就是0它不用赋值 
			if(len==0)i++;
			else len=nxt[len-1];//不然就让len再次退
			//不难发现它此处复制的是nxt[len-1]
			//这里有一个很妙的点：nxt[len-1]它既是长度又可以做下一个下标
			//因为string 是从零开始的 
			// 当前 s2[i] != s2[len]，说明 len 长度的前缀无法继续匹配
			// 退而求其次，找更短的前缀：len = nxt[len-1]
			// nxt[len-1] 表示 s2[0..len-1] 的最长相等前后缀长度
			// 这个长度恰好也是下一个要尝试匹配的位置
		}
	}
	int j;
	i=j=0;
	//i是s1的指针，j是s2的指针 
	while(i<s1.size()){
		//如果刚好能够匹配上，那就都+1 
		if(s1[i]==s2[j]){
			i++,j++;
		}else{
			//如果不能匹配上（这里其实和nxt的处理几乎一样） 
			if(j==0)i++;//退无可退++ 
			else j=nxt[j-1];//还能退，就继续退 
		}
		//输出位置 
		if(j==s2.size())cout<<i-j+1<<endl;
		//不需要重置，下一次nxt[j-1]会往回退 
	}
	//输出nxt[i] 
	for(int i=0;i<s2.size();i++)cout<<nxt[i]<<" ";
	return 0;
}

考试的核心是以nxt数组为核心。（毕竟浓缩的是精华）
考点在于前后缀，循环节。
跳nxt数组可以用倍增优化。

Next One!
https://www.luogu.com.cn/problem/P4391

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int nxt[N];
int main(){
	int n;
	string a;
	cin>>n>>a;
	int j=1,len=0;
	while(j<a.size()){
		if(a[j]==a[len]){
			nxt[j++]=++len;
		}else{
			if(len==0)j++;
			else len=nxt[len-1];
		}
	}
	cout<<n-nxt[n-1];
	return 0;
}

这是一个相当典型的kmp相关的trick（感觉能算是trick）
需要一个奇怪的证明。（接下来的图片from洛谷第一篇题解）

懒洋洋地放置一下代码：

https://www.luogu.com.cn/problem/P5829
失配树

——————————————————————————————————————————

字典树 Trie

将很多个前缀相同的单词放置在一棵树上（？）
1.支持查找某个字符串是否在集合中
2.查询集合中有多少字符串给定字符串为前缀

初学字典树，先来梳理一下它的框架

1.插入
（接下来的代码和图片建议配合使用）

画完图才发现没有加cnt。
这边有一个需要注意的点：关于trie数组的大小和其定义。
先搞清楚它的定义：Trie[i][j]：在节点i上遇到字符j应该去哪个节点。
第一维就是所有字符串长度。第二位就看你是怎么去把字符变成数字的，由于本题是大写+小写，所以建议开52.

2.查询

没了。

放置代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5;
int tri[N][65],idx,cnt[N];
int change(char x){
	if(x>='a'&&x<='z')return x-'a'+26;
	if(x>='0'&&x<='9')return x-'0'+52;
	return x-'A';
}
void ins(string a){
	int p=0;
	for(int i=0;i<a.size();i++){
		int c=change(a[i]);
		if(!tri[p][c])tri[p][c]=++idx;
		p=tri[p][c];
		cnt[p]++;
	}
}
int find(string s){
	int p=0;
	for(int i=0;i<s.size();i++){
		int c=change(s[i]);
		if(!tri[p][c])return 0;
		p=tri[p][c];
	}
	return cnt[p];
}
int main(){
	int T;
	cin>>T;
	while(T--){
		int n,q;
		cin>>n>>q;
		for(int i=0;i<=idx;i++){
			for(int j=0;j<=63;j++){
				tri[i][j]=0;
			}
		}
		for(int i=0;i<=idx;i++)cnt[i]=0;
		idx=0;
		for(int i=1;i<=n;i++){
			string s;
			cin>>s;
			ins(s);
		}
		for(int i=1;i<=q;i++){
			string s;
			cin>>s;
			cout<<find(s)<<'\n';
		}
	}
	return 0;
}