数据结构——模式匹配KMP

发表于 2024-10-15 更新于 2024-10-28 分类于大二上，数据结构

数据结构——模式匹配KMP

前言

以前因为惰性，没有记录学习笔记的习惯，但我决定抛弃过去，从现在出发，既要有摒弃过去的决心，又要有继续前进的勇气，悟以往之不谏，知来者之可追。

题目

对于字符串s，查找是否有子串t，并用字符串m替换

暴力解法——BF

具体操作步骤如下：

从文本的第一个字符开始，与模式的第一个字符进行逐一比较。
如果模式的每个字符都与文本中的相应字符匹配，则匹配成功，返回当前匹配的位置。
如果某个字符不匹配，则从文本的下一个字符开始重新进行比较。
重复步骤1-3，直到找到匹配或文本搜索完毕。

由于每次比较都要逐一对齐模式串和文本，最坏情况下的时间复杂度是 O(m * n)

//编写替换函数
string replace(string& s, string& t,string& m, int start)
{
	int len1 = s.length();
	int len2 = m.length();
	int len3 = t.length();
	string temp;
	for (int i = 0; i < start; i++)
	{
		temp += s[i];
	}
	temp += m;
	for (int i = start + len3; i < len1; i++)
	{
		temp += s[i];
	}
	return temp;
}

void BFmatching(string &s, string &t, string &m)
{
	int i = 0;
	int j = 0;
	int len1 = s.length();
	int  len2 = t.length();
	int len3 = m.length();
	while (i < len1)
	{
		if (s[i] == t[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;
			j = 0;
		}
		
		if (j >= len2)
		{
			s = replace(s, t, m, i - j);
			len1 = s.length(); // 更新字符串的长度
			i = i - j + len3;
			j = 0;
		}
		
	}
	
}

KMP算法

前缀和后缀

前缀：从字符串的 第一个字符 开始的连续子串。前缀的长度可以从0到字符串的总长度减1。注意，前缀不包括整个字符串本身。

后缀：从字符串的 最后一个字符 开始的连续子串。与前缀类似，后缀的长度也可以从0到字符串的总长度减1。后缀不包括整个字符串本身。

二者意义：简单来说，就是当前匹配的后缀与前缀相同时，便可以跳过前缀的比较，直接开始后面的比较，而next数组则记录的是最长的既是前缀又是后缀的公共子串的长度，同样也是回溯的位置

next数组的生成

vector<int> getnext(string& t)
{
	int len = t.length();
	vector<int> next(len, 0);
	int i= 0;//后缀
	int j = 0;//前缀末尾的位置，也是前缀的长度
	next[0] = 0;
	for (i = 1; i < len; i++)
	{
		while (j > 0 && t[i] != t[j])
		{
			j = next[j - 1];
		}
		if (t[i] == t[j])
		{
			j++;
		}
		next[i] = j;
	}
	return next;
}

利用后缀指针i和前缀指针j，在后缀指针不断向后遍历的过程中：

如果可以匹配，则前缀指针i向后移动一位
如果不可以匹配，则前缀指针向前回溯

KMP算法的匹配

void KMPmatching(string& s, string& t, string& m)
{
	vector<int> next = getnext(t);
	int len1 = s.length();
	int len2 = t.length();
	int len3 = m.length();
	int i = 0,j = 0;
	while (i < len1) {
		if (s[i] == t[j]) {
			i++;
			j++;
		}
		else {
			if (j != 0) {
				j = next[j - 1];//向前回溯
			}
			else {
				i++;
			}
		}

		// 完成匹配后进行替换
		if (j == len2) {
			s = replace(s, t, m, i - j);
			len1 = s.length(); // 更新字符串的长度
			i = i - j + m.length(); // 从替换后的新位置继续查找
			j = 0; // 重置 j 以重新开始匹配
		}
	}
}

反思

注意更新s字符串的长度，每次替换后，s字符串都会变化，需要进行更新，否则运行是会造成溢出

参考文献

帮你把KMP算法学个通透！（理论篇）_哔哩哔哩_bilibili

帮你把KMP算法学个通透！（求next数组代码篇）_哔哩哔哩_bilibili

我一直觉得写文章是一件很酷的事情，但奈何自己文采实在有限，又没有练习写作读书的勤奋劲，所以一直搁置，还记得刚上大学那一阵，看了两位学长自己搭的博客，写了很多自己的文章，记录着自己的成长，不仅是对自己成长的记录，也是对后辈的鼓励和启示，真的让我十分崇拜与鼓舞，于是就在心中埋下搭建自己心中埋下搭建自己博客的种子，但因学业和惰性一直搁置下来，还有个重要原因就是，我不知道我的博客应该写些什么，这使我没有动力继续前进。

直到前阵子，我与我的父亲在车上谈话，他与我聊起了他年轻时做贸易的故事，他说他对市场的判断总能先于他人，甚至08年金融危机，他也做出了正确的判断，他与我分享说，他一个很重要的习惯就是，把他读书看新闻遇到的信息整合，实实在在地写下来，记录下来到一个本子上。可能这对别人觉得很正常，但我却很震撼，我没想到不光是我的同龄人们这样做，我的父母辈也是如此，这样一个宝贵的经验我实在应该学习。

现在我已经步入大二，接触的事物也比大一扩展了很多，我绝对不能再等待，即使现在写不好，只要开始就是进步，后面我希望能把我的所思所想，进步痕迹通通记录下来，我的博客不光是我的名片，让大家更好地了解我，也是我自己宝贵的回忆！

简历备份

发表于 2024-10-14 分类于随笔

🧑‍💻 张熙浚
电话：18114477496｜个人网站：https://zxj-2023.github.io/

教育背景
南京师范大学 - 本科 - 人工智能专业（2023.09-2027.07） 211 双一流
- 语言：英语（CET4，589）
- 校内任职：现任院学生会主任、班级学习委员；
- 绩点综测：绩点综测排名均列专业前二；
- 校园经历：在三次获得校优秀学生奖学金一等奖，校优秀学习奖，校三好学生；
个人荣誉
- 全国大学生计算机设计大赛 - 全国级三等奖 (2024)
- 全国大学生数学建模大赛 - 江苏省一等奖 (2024)
- 全国大学生蓝桥杯程序算法设计 - 江苏省三等奖
- 大学生创新创业项目 - 省重点项目 (2024)
- 蓝桥杯AIGC 数字内容创意设计大赛 - 国家级三等奖（2024）
项目经验
计算机设计大赛 - 基于 unity 的 2.5D 国风游戏设计 -（2024.03 - 2024.06）
- 围绕《九章算术》设计并开发了四大游戏场景，多个小游戏，动画，对话系统和ui界面。
- 在unity平台实现2.5D场景构建，利用playmaker插件实现可视化编程。
- 使用C#脚本完成游戏逻辑构建。
计算机设计大赛 - 基于 LightRAG 的本地安全大模型 -（2024.10 - 至今）
- 完成LightRAG与GraphRAG的对比，利用LightRAG实现知识检索增强功能,并利用neo4j实现知识图谱可视化。
- 采用pycharm+anaconda集成开发环境，使用ollama框架完成本地大模型部署。
- 后续会进行大模型的微调，数据集的清洗，网站搭建等工作。
25 年大学生创新创业项目 - 基于多模态特征融合的视频暴力行为识别方法研究 -（2024.09 - 至今）
- 完成了一种基于多模态特征融合的视频暴力行为识别算法，通过融合RGB模态、帧差模态以及Depth模态，使其能够准确、鲁棒地在复杂的真实环境下进行暴力行为识别。
- 完成了一种自适应的注意力算法用于多模态融合。让模型自适应地学习不同模态特征之间的权重关系。
- 完成了系统的设计，后续会继续进行开发。
竞赛经验
全国大学生数学建模大赛 - 江苏省一等奖 - （2024.09）
认证杯数学建模大赛（小美赛）- s奖 -（2024.12）
- 担任编程手一职，协同建模手完成了部分公式的推导等
蓝桥杯AIGC中数杯 - 国家级三等奖 -（2024.10）
- 利用市面上现有AIGC技术完成视频制作，实现docker部署stable Diffusion
自我评价
- 交际能力强，具备良好的口头表达和书面沟通能力，长于社交，具备丰富的活动组织经验
- 学习能力强，陌生的知识与技术会积极学习，会积极请教问题并听取建议

Zhang XiJun