AkiraZheng's Time.

KMP算法

Word count: 386Reading time: 1 min
2024/04/29

前言

最主要是掌握KMP算法的next数组的构建过程，具体的解法看参考的文章，讲得很好

一、KMP算法Next构建

二、代码实现（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void getNext(vector<int> &next, string templateStr) {
	int i = 0;//后缀结尾
	int j = 0;//前缀结尾

	int str_size = templateStr.size();
	next = vector<int>(str_size);
	next[0] = 0;

	for (i = 1; i < str_size; ++i) {
		//前缀跟后缀不相等的话，说明得往前查找
		while (j > 0 && templateStr[j] != templateStr[i]) {
			j = next[j-1];
		}

		//前缀跟后缀相等的话，说明可以往后移一位了
		if (templateStr[j] == templateStr[i]) {
			++j;
		}

		//构建当前后缀的最长前缀
		next[i] = j;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int KMP(vector<int>& next, string templateStr, string searchStr) {
	int i = 0;//searchStr的
	int j = 0;//templateStr的

	for (; i < searchStr.size(); ++i) {
		//跟模板不相等则跳转到模板对应的位置
		while (j > 0 && templateStr[j] != searchStr[i]) {
			j = next[j-1];
		}

		//跟模板相等则模板指针加一，说明可以对下一个字符进行判断
		if (templateStr[j] == searchStr[i]) {
			++j;
		}

		//已经找全了（模板指针指向末尾）
		if (j == templateStr.size()) return i-templateStr.size()+1;
	}

	//没找到
	return -1;
}

三、测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int main() {

	vector<int> next;
	string s = "ababaca";

	myKMP kmp;
	kmp.getNext(next, s);
	for (int i = 0; i < s.size(); ++i) {
		cout << next[i] << " ";
	}
	cout << endl;

	cout << kmp.KMP(next, s, "bacbababadababacambabacaddababacasdsd");

	return 0;
}

四、相关leetcode题目

总结

参考：字符串匹配KMP算法的讲解C++

Author：AkiraZheng

Link：https://akirazheng.github.io/2024/04/29/KMP%E7%AE%97%E6%B3%95/

Publish date：April 29th 2024, 8:22:31 pm

Update date：April 29th 2024, 9:48:54 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 前言
  2. 一、KMP算法Next构建
  3. 二、代码实现（C++）
  4. 三、测试
  5. 四、相关leetcode题目
  6. 总结
Total : 41
2024
2023
2022
杂货铺-休闲 环境配置 计算机 深度学习
动手学深度学习 重装-环境配置-计算机 C++知识点 计算机网络 数据库 WebServer项目（C++） 数据结构与算法 设计模式 操作系统 系统设计