KMP算法
2021/6/13 22:21:46
本文主要是介绍KMP算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1. 原理:“移动位数 = 已匹配的字符数 - 对应的部分匹配值”;
为了计算简明,可以将原理的跳转方法记录在next数组中(next数组以0开始还是-1开始都可以);
next[j] 的含义是:在子串的第j个字符与主串不匹配时,把子串的next[j]位置移动至与主串当前位置比较;
因此KMP算法的主要过程就在于求子串的next数组了。
2. nextval数组:对next数组进一步改进,如果跳转到的next[j]位置的字符与当前字符一样,那肯定还是不匹配,所以应该继续递归,也就是将next[j]修正为next[next[j]],直至与当前字符不相等,如此修改的数组记为nextval。
3. 匹配过程:如果next[j]==-1,则主串后移一位;否则把模式串跳到next[j]位置继续匹配。
整个过程中主串指针不回移,求next需要O(m),匹配一遍O(n),总共O(m+n)。
4. 例题:S="ababaaababaa"
next:011234223456
nextval:010104210104
5. 代码实现:leetcode28
class Solution { public: int strStr(string haystack, string needle) { return kmp(haystack,needle); } int kmp(string s,string t){ int i=0,j=0; int len1=s.size(),len2=t.size(); if(len2==0)return 0; vector<int> next=get_nextval(t); while(i<len1&&j<len2){ if(j==-1||s[i]==t[j]){//该位匹配或者需要从下一位重来 ++i,++j; }else{ j=next[j]; } } if(j==len2)return i-len2; return -1; } vector<int> get_nextval(string t){ int len=t.size(); vector<int> nextval(len); nextval[0]=-1; int i=0,j=-1; while(i<len-1){ if(j==-1||t[i]==t[j]){//匹配了,按照记录+1给next赋值 ++i,++j; if(t[i]!=t[j])nextval[i]=j; else nextval[i]=nextval[j]; }else{//没匹配,循环继续 j=nextval[j]; } } return nextval; } };
这篇关于KMP算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南