c++ KMP子串查找算法怎么用

这篇文章主要介绍了c++ KMP子串查找算法怎么用的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇c++ KMP子串查找算法怎么用文章都会有所收获，下面我们一起来看看吧。

我们在之前学习了字符串类，那么查找字符串类的需求就随之而来。如何在目标字符串 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子串查找算法怎么用"知识都有一定的了解，大家如果还想学习更多知识，欢迎关注行业资讯频道。