c++ KMP字符串匹配算法

目录
  • KMP算法简介
  • 前缀表
  • 如何构造前缀表next数组
  • 如何用next数组进行模板匹配
  • 总结

KMP算法简介

KMP算法(Knuth-Morris-Pratt 算法)是一个著名的字符串匹配算法，它主要的思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配。

本章以力扣 28. 实现 strStr()为例子进行讲解。

力扣28.实现strStr()函数：给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

说明：当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当 needle 是空字符串时我们应当返回 0 。

示例 1： 输入：haystack = "hello", needle = "ll"        输出：2

此题若用暴力解法代码如下：

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n=haystack.size(),m=needle.size();
        if(m==0) return 0;
        for(int i=0;i<n;i++){
            if(haystack[i]==needle[0]){
                for(int j=0;j<m;j++){
                    if(haystack[i+j]!=needle[j])
                        break;
                    if(j==m-1) return i;
                }
            }
        }
        return -1;
    }
};

可见暴力匹配过程中实现的是一个双层循环，那么算法的时间复杂度较高，为О(n*m)，然而KMP的算法时间复杂度仅为О(n+m)，其算法性能明显提高，具体时间复杂度计算方法后面介绍。

前缀表

KMP算法中一个重要的概念就是前缀表（prefix table），并用一维数组 next 记录前缀信息实际上next数组就是一个前缀表。

了解前缀表我们首先需要了解前缀和后缀的区别，此处的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串，后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。比如字符串“abac”的前缀有“a”, "ab”, "aba”，字符串“abac”的后缀有“c”,"ac”，"bac”。

前缀表第 i 个位置存的值 next[i] 代表[0,i]这个字符串最长的相同前后缀的长度，比如字符串“abbc”的 next[3]为 0 ,next[2]为 1 ("aba”的前缀有“a”, "ab”，后缀有“a”,"ba”)。

前缀表的作用是用来记录了模板串与主串(文本串)不匹配的时候，模板串应该从哪里开始重新匹配。

KMP算法的核心思想就是先求出匹配模板的next数组，再运用next数组进行字符串匹配。

如何构造前缀表next数组

void get_next(int *next,string t){ //t为模板字符串
        //定义两个指针prefix和suffix，prefix指向前缀起始位置，suffix指向后缀起始位置
        int prefix=0;
        next[prefix]=0;
        for(int suffix=1;suffix<t.size();suffix++){
            while(prefix>0 && t[suffix]!=t[prefix]){//前后缀不相同，前缀指针向前回退
                prefix=next[prefix-1];
            }
            if(t[suffix]==t[prefix]){//前后缀相同，前缀指针前进一位
                prefix++;
            }
            next[suffix]=prefix;//更新next数组，prefix走到哪说明就有多少的相同的前后缀
        }
    }

如何用next数组进行模板匹配

int strStr(string haystack, string needle) {
        if(needle.size()==0) return 0;
        int next[needle.size()];
        get_next(next,needle);
        int j=0;
        //定义两个下标j指向模版串起始位置，i指向文本串起始位置
        for(int i=0;i<haystack.size();i++){
            while(j>0 && haystack[i]!=needle[j]){ //模版串j位置和文本串i位置不相同，j利用next数组回退到上一个相同的位置继续匹配
                j=next[j-1];
            }
            if(haystack[i]==needle[j]){  //模版串j位置和文本串i位置相同
                j++;
            }
            if(j==needle.size()){  //找到匹配的字符串
                return (i-needle.size()+1); //返回匹配的字符串起始位置
            }
        }
        return -1;
    }

由此可见构造next数组的时间复杂度是О(m)，利用next数组进行匹配的时间复杂度是О(n)，总的时间复杂度是О(n+m)

总结

到此这篇关于c++ KMP字符串匹配算法的文章就介绍到这了,更多相关c++ KMP字符串匹内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 一篇文章带你了解C++的KMP算法

    目录 KMP算法 步骤1:先计算子串中的前后缀数组Next C++代码: 步骤2:查找子串在母串中出现的位置. 总结 KMP算法 KMP算法作用:字符串匹配 例如母串S = "aaagoogleaaa"; 子串T= "google"; 步骤1:先计算子串中的前后缀数组Next g o o g l e next[0] next[1] next[2] next[3] next[4] next[5] -1 0 0 0 1 0 C++代码: //步骤1: void GetN

  • C++ 数据结构之kmp算法中的求Next()函数的算法

    C++ 数据结构之kmp算法中的求Next()函数的算法

    C++ 数据结构之kmp算法中的求Next()函数的算法 实例代码: #include <iostream> using namespace std; void preKmp(char *c, int m, int Next[]) { int i=1,j=-1; Next[0]=-2; while(i<m) { if(j==-2) { Next[i]=-1; i++; j=-1; } ++j; if(i==m) return; if(c[i]==c[j]) { Next[i]=j; ++

  • c++ 实现KMP算法

    KMP KMP算法解决的问题 字符串str1和str2,str1是否包含str2,如果包含返回str2在str1中开始的位置. 如何做到时间复杂度O(N)完成? 思路: 首先判断两个字符串是否为空串,并且str2的长度是否小于str1的长度,因为题目要求str1中包含str2. 以上都满足的情况下,首先定义两个变量分别为 x ,y 作为后续字符串中字符遍历的下标,然后再生成一个vector容器next,用来后续的匹配加速 然后在str2中,做加速操作,也就是 看当前 i - 1和之前的所有字符,

  • c++ KMP字符串匹配算法

    目录 KMP算法简介 前缀表 如何构造前缀表next数组 如何用next数组进行模板匹配 总结 KMP算法简介 KMP算法(Knuth-Morris-Pratt 算法)是一个著名的字符串匹配算法,它主要的思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配. 本章以力扣 28. 实现 strStr()为例子进行讲解. 力扣28.实现strStr()函数:给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 n

  • Python字符串匹配算法KMP实例

    本文实例讲述了Python字符串匹配算法KMP.分享给大家供大家参考.具体如下: #!/usr/bin/env python #encoding:utf8 def next(pattern): p_len = len(pattern) pos = [-1]*p_len j = -1 for i in range(1, p_len): while j > -1 and pattern[j+1] != pattern[i]: j = pos[j] if pattern[j+1] == pattern

  • php中最简单的字符串匹配算法

    本文实例讲述了php中最简单的字符串匹配算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: <?php /* 最简单字符串匹配算法php实现方式   T: ababcabc P: abc   0.          1.          2. ababcabc    ababcabc    ababcabc |||          |||          ||| abc          abc          abc (X)          (X)         

  • 多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法在这里指的是在一个字符串中寻找多个模式字符字串的问题.一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的.该算法广泛应用于关键字过滤.入侵检测.病毒检测.分词等等问题中.多模问题一般有Trie树,AC算法,WM算法等等. 背景 在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下 for (String document : d

  • Python实现字符串匹配算法代码示例

    字符串匹配存在的问题 Python中在一个长字符串中查找子串是否存在可以用两种方法:一是str的find()函数,find()函数只返回子串匹配到的起始位置,若没有,则返回-1:二是re模块的findall函数,可以返回所有匹配到的子串. 但是如果用findall函数时需要注意字符串中存在的特殊字符 蛮力法字符串匹配: 将模式对准文本的前m(模式长度)个字符,然后从左到右匹配每一对对应的字符,直到全部匹配或遇到一个不匹配的字符.后一种情况下,模式向右移一位. 代码如下: def string_m

  • PHP实现的字符串匹配算法示例【sunday算法】

    本文实例讲述了PHP实现的字符串匹配算法----sunday算法.分享给大家供大家参考,具体如下: Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配.其核心思想是:在匹配过程中,模式串发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率. <?php /* *@param $pattern 模式串 *@param $text 待匹配串 */ function mySunday($pattern = '',$text = ''){ if(!$

  • 浅谈JAVA字符串匹配算法indexOf函数的实现方法

    前言 相信每个学习过Java的人都使用过indexOf函数,indexOf函数我们可以查找一个字符串(模式串)是否在另一个字符串(主串)出现过,返回结果表示出现位置的下标,如果返回-1,表示模式串在主串中不存在,那么,你可曾想过这些查找函数又是如何实现的呢? 从indexOf源码看起 首先我们先来看一下indexOf的源码,indexOf的使用方式比较多,这是我们以一个形参的为例. static String mainString = "Hello my name is HuangLinqing

  • Java 分割字符串详解及实例代码

     Java 分割字符串 java.lang.String 的 split() 方法, JDK 1.4 or later public String[] split(String regex,int limit) 示例代码 public class StringSplit { public static void main(String[] args) { String sourceStr = "1,2,3,4,5"; String[] sourceStrArray = sourceSt

  • Java中分割字符串的两种方法实例详解

    前言 相信大家应该都知道在java编程中,有时候我们需要把一个字符串按照某个特定字符.字母等作为截点分割这个字符串,这样我们就可以使用这个字符串的一部分或者把所有截取的内容保存到数组里等操作.下面这篇文章就给大家分享了两种分割的方法,下面来一起看看吧. 一.java.lang.String 的 split() 方法, JDK 1.4 or later public String[] split(String regex,int limit) 示例代码 public class StringSpl

  • 使用C语言解决字符串匹配问题的方法

    最常想到的方法是使用KMP字符串匹配算法: #include <stdio.h> #include <stdlib.h> #include <string.h> int get_nextval(char *pattern, int next[]) { //get the next value of the pattern int i = 0, j = -1; next[0] = -1; int patlen = strlen(pattern); while ( i &l

随机推荐