扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
这篇文章主要介绍了c++ KMP子串查找算法怎么用的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇c++ KMP子串查找算法怎么用文章都会有所收获,下面我们一起来看看吧。
成都创新互联公司主营宿松网站建设的网络公司,主营网站建设方案,App定制开发,宿松h5成都微信小程序搭建,宿松网站营销推广欢迎宿松等地区企业咨询我们在之前学习了字符串类,那么查找字符串类的需求就随之而来。如何在目标字符串 S 中,查找是否存在子串 P?
我们大家最先能想到的肯定是朴素解法,何谓朴素解法呢?就是一个一个进行对比,如果比对不成功,便向后移一位。代码如下
那么此时的解法肯定不太好,因为它的时间复杂度为 O(m*n)。那么我们该如何对其进行优化呢?我们来看看下图
由上图我们可以得出一个结论:因为 Pa !=Pb 且 Pb == Sb;所以 Pa!+ Sb;因此,子串 p 右移 1 位是没有意义的。接下来我们以示例字符串为例来进行分析说明,如下
我们看到在第一步的时候,第 1 个字符就匹配失败,然后我们直接右移 1 位;直至第 7 个字符匹配失败,此时我们通过肉眼观察可知,右移 4 位是最好的;接下来在匹配到第 3 个字符的时候又失败了,通过肉眼观察可知,右移 2 为是最好的;后面以此类推。
那么我们是否有什么发现呢?只要我们能知道需要右移几位,我们便可以轻易的得出结论。那么这块就有前人已经发现了规律,我们只需掌握这个方法即可轻易的解决问题。那么伟大的发现是什么呢?在匹配失败时的右移位数与子串本身相关与目标串无关;移动位数 = 已匹配的字符数 - 对应的部分匹配值;任意子串都存在一个唯一的部分匹配表。
下来我们来看看一个部分匹配表的示例,如下
那么问题来了,这个部分匹配表是如何得到的呢?首先我们来介绍两个概念:前缀和后缀。前缀是指除了最后一个字符以外,一个字符串的全部头部组合;后缀是指除了第一个字符以外,一个字符串的全部尾部组合。那么部分匹配值便是前缀和后缀最长共有元素的长度,我们以字符串 “ABCDABD” 为例来进行分析,如下图所示
我们看到在第一个字符 A 的时候,它的交集为空,因此匹配值为 0;在前两个字符时,同样为空,因此匹配值也为空;直至第5个字符时,交集为 A,因此它的匹配值为 1;第 6 个字符时,交集为 AB,因此此时的匹配值为 2;最后一个字符时,交集为空,因此匹配值为 0。
那么我们知道了如何手动的求解部分匹配值,那么如何在程序中编程产生部分匹配表呢?
实现关键:
1、PMMT[1] = 0(下标为 0 的元素匹配值为 0)
2、从 2 个字符开始递推(从下标为 1 的字符开始递推)
3、假设 PMT[n] = PMT[n-1] + 1(最长共有元素的长度)
4、当假设不成立,PMT[n] 在 PMT[n-1] 的基础上减小
下来我们来实现部分匹配表的程序,代码如下
#include#include #include "DTString.h" using namespace std; using namespace DTLib; int* make_pmt(const char* p) // O(n) { int len = strlen(p); int* ret = static_cast (malloc(sizeof(int) * len)); if( ret != NULL ) { int ll = 0; ret[0] = 0; for(int i=1; i 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 我们来看看结果是否和我们上面推导的是一样的?
我们看到结果是0 0 0 0 1 2 0,和我们上面手动推导出来的结果是一致的,因此这个部分匹配表的代码编写是正确的。下来我们就来看看部分匹配表的使用(KMP 算法):下标 j 处匹配失败 --> 前 j 位匹配成功 --> 查表 PMT[j-1] --> 右移位数 j-PMT[j-1]。如下图所示
因为 s[i] != p[j], 所以查表可知,LL= PMT[j-1]。于是乎,右移,i 的值不变,j 的值改变,j = j - (j-LL) = LL = PMT[j-1]。
下来我们来看看 KMP 子串查找算法的具体实现,如下
#include#include #include "DTString.h" using namespace std; using namespace DTLib; int* make_pmt(const char* p) // O(n) { int len = strlen(p); int* ret = static_cast (malloc(sizeof(int) * len)); if( ret != NULL ) { int ll = 0; ret[0] = 0; for(int i=1; i 0) && (p[ll] != p[i]) ) { ll = ret[ll-1]; } if( p[ll] == p[i] ) { ll++; } ret[i] = ll; } } return ret; } int kmp(const char* s, const char* p) // O(m) + O(n) ==> 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 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; } int main() { cout << kmp("abcde", "cd") << endl; cout << kmp("ababax", "d") << endl; return 0; } 我们来看看结果,如下
关于“c++ KMP子串查找算法怎么用”这篇文章的内容就介绍到这里,感谢各位的阅读!相信大家对“c++ KMP子串查找算法怎么用”知识都有一定的了解,大家如果还想学习更多知识,欢迎关注创新互联网站制作公司行业资讯频道。
分享文章:c++KMP子串查找算法怎么用-创新互联
网站链接:http://kswjz.com/article/cdocis.html
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流