c++KMP子串查找算法怎么用-创新互联-成都快上网建站

c++KMP子串查找算法怎么用-创新互联

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

成都创新互联公司主营宿松网站建设的网络公司,主营网站建设方案,App定制开发,宿松h5成都微信小程序搭建,宿松网站营销推广欢迎宿松等地区企业咨询

       我们在之前学习了字符串类,那么查找字符串类的需求就随之而来。如何在目标字符串 S 中,查找是否存在子串 P?

       我们大家最先能想到的肯定是朴素解法,何谓朴素解法呢?就是一个一个进行对比,如果比对不成功,便向后移一位。代码如下

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

       那么此时的解法肯定不太好,因为它的时间复杂度为 O(m*n)。那么我们该如何对其进行优化呢?我们来看看下图

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

       由上图我们可以得出一个结论:因为 Pa !=Pb 且 Pb == Sb;所以 Pa!+ Sb;因此,子串 p 右移 1 位是没有意义的。接下来我们以示例字符串为例来进行分析说明,如下

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

       我们看到在第一步的时候,第 1 个字符就匹配失败,然后我们直接右移 1 位;直至第 7 个字符匹配失败,此时我们通过肉眼观察可知,右移 4 位是最好的;接下来在匹配到第 3 个字符的时候又失败了,通过肉眼观察可知,右移 2 为是最好的;后面以此类推。

       那么我们是否有什么发现呢?只要我们能知道需要右移几位,我们便可以轻易的得出结论。那么这块就有前人已经发现了规律,我们只需掌握这个方法即可轻易的解决问题。那么伟大的发现是什么呢?在匹配失败时的右移位数与子串本身相关与目标串无关;移动位数 = 已匹配的字符数 - 对应的部分匹配值;任意子串都存在一个唯一的部分匹配表。

       下来我们来看看一个部分匹配表的示例,如下

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

       那么问题来了,这个部分匹配表是如何得到的呢?首先我们来介绍两个概念:前缀和后缀。前缀是指除了最后一个字符以外,一个字符串的全部头部组合;后缀是指除了第一个字符以外,一个字符串的全部尾部组合。那么部分匹配值便是前缀和后缀最长共有元素的长度,我们以字符串 “ABCDABD” 为例来进行分析,如下图所示

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

       我们看到在第一个字符 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

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

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

       我们看到结果是0 0 0 0 1 2 0,和我们上面手动推导出来的结果是一致的,因此这个部分匹配表的代码编写是正确的。下来我们就来看看部分匹配表的使用(KMP 算法):下标 j 处匹配失败 --> 前 j 位匹配成功 --> 查表 PMT[j-1] --> 右移位数 j-PMT[j-1]。如下图所示

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

       因为 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子串查找算法怎么用”知识都有一定的了解,大家如果还想学习更多知识,欢迎关注创新互联网站制作公司行业资讯频道。


分享文章:c++KMP子串查找算法怎么用-创新互联
网站链接:http://kswjz.com/article/cdocis.html
扫二维码与项目经理沟通

我们在微信上24小时期待你的声音

解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流