KMP算法学习记录
2022/8/28 1:22:46
本文主要是介绍KMP算法学习记录,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
KMP算法
作用:用于字符串匹配。
1 准备
前缀:指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀:指不包含第一个字符的所有以最后一个字符结尾的连续子串。
next[](前缀表):最长前后缀数组。
j是从1开始的;
2 实现
2.1 求next[]
//如果相等长度+1 if(needle[i] == needle[j]){ j++; next[i] = j; }else{ //回退 j = next[j - 1]; }
完整代码
vector<int> get_next(string& t){ vector<int> next(t.size(), -1); /* j的初始值为-1,值整体右移一位, 这样j对应的位置就是他应该回退的坐标,否则他的前一位才是应该回退的值 */ int i= 0, j = -1; while(i < t.size() - 1){ if(j == -1 || t[i] == t[j]){ j++; i++; next[i] = j; }else{ j = next[j]; } } return next; }
2.2 匹配算法
int strStr(string s, string t) { if (t.length() == 0) { return 0; } int n = s.length(); int m = t.length(); vector<int> next = get_next(t); int i = 0, j = 0; while( i < n && j < m){ if(j == -1 || s[i] == t[j]){ j++; i++; if (j == m ) return i - m ; }else{ j = next[j]; } } //未找到返回-1 return -1; }
3 改进next[]
我们发现2 3 4 5都是多余的判断,因此next[]得到了改良 nextval[]。
vector<int> get_nextval(string& t){ vector<int> nextval(needle.size(), -1); int i= 0, j = -1; while(i < t.size() - 1){ if(j == -1 || t[i] == t[j]){ j++; i++; //如果与s[next[i]]相等则取之前的值 if(t[i] == t[j]){ nextval[i] = nextval[j]; }else{ //如果不等,取现在的值 nextval[i] = j; } }else{ j = nextval[j]; } } return nextval; }
匹配代码不需要改动,只需要next[]替换为nextval[]即可。
这篇关于KMP算法学习记录的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-0601-电商商品中心解密:仅凭SKU真的足够吗?
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能