数据结构——模式匹配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 以重新开始匹配
		}
	}
}