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 <iostream>
#include <cstring>
#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<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;
}

        我们来看看结果是否和我们上面推导的是一样的？

        我们看到结果是 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 <iostream>
#include <cstring>
#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<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 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<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;
}

int main()
{
    cout << kmp("abcde", "cd") << endl;
    cout << kmp("ababax", "d") << endl;

    return 0;
}

        我们来看看结果，如下

关于“c++ KMP子串查找算法怎么用”这篇文章的内容就介绍到这里，感谢各位的阅读！相信大家对“c++ KMP子串查找算法怎么用”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注亿速云行业资讯频道。