KMP子串查找算法
2022/1/15 22:04:25
本文主要是介绍KMP子串查找算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
那么部分匹配表怎么获得?
实现关键
- PMT[1]=0;(下标为0的元素匹配值为0)
- 从2个字符开始递推(从下标为1的字符开始递推)
- 假设PMT[n]=PMT[n-1]+1(最长共有元素的长度)
- 当假设不成立,PMT[n]在PMT[n-1]的基础上减小
部分匹配表是前辈找到的规律,不需要理解,会用就行!
获得部分匹配表函数如下:
int* make_pmt(const char* p) { int len = strlen(p); int* ret = static_cast<int*>(malloc(sizeof(int)*len)); if(ret != NULL) { int ll=0; ret[0]=0; for(int i=1;i<len;i++) { while( (ll>0) && (p[ll]!=p[i])) { ll = ret[ll-1]; } if( p[ll] == p[i] ) { ll++; } ret[i]=ll; } } return ret; }
测试:
int main() { int* pmt = make_pmt("abcdabd"); for(int i=0;i<strlen("abcdabd");i++) { cout << i << ":" << pmt[i] << endl; } return 0; }
和上面一致
KMP算法实现:
int kmp(const char* s,const char* p)//O(m+n) { int ret = -1; int sl=strlen(s); int pl=strlen(p); int* pmt=make_pmt(p); if((pmt != NULL) && (0<pl) && (pl<=sl)) { for(int i=0,j=0;i<sl;i++) { while((j>0) && (s[i] != p[j])) { j = pmt[j-1]; } if(s[i] == p[j]) { j++; } if(j == pl)//查找到 { ret = i+1-pl; break; } } } free(pmt); return ret; }
这你妈是人能写出来的?
这篇关于KMP子串查找算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南