c++KMP字符串匹配算法

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字符串匹内容请搜索易知道(ezd.cc)以前的文章或继续浏览下面的相关文章希望大家以后多多支持易知道(ezd.cc)!

推荐阅读

    字符库快捷键|字符串快捷键

    字符库快捷键|字符串快捷键,,1. 字符串快捷键1、单行注释单行注释是 #Mac的快捷键是 command+/windows的快捷键是 Ctrl + /2、多行注

    数列求和快捷键|数组求和快捷键

    数列求和快捷键|数组求和快捷键,,数组求和快捷键1,这是文本型数组直接运算 不可能 除非单个的取出来分割后转数值型,再找相同的X[1],进行X[2

    电脑十进制算法|十进制的算法教程

    电脑十进制算法|十进制的算法教程,,十进制的算法教程0x10就是十六进制数10,转换为十进制数是16,即10(十六进制) = 16(十进制)。十六进制转换

    伪代码描述算法

    伪代码描述算法,算法,描述,伪代码,自然语言,语言,编程语言,  伪代码是自然语言和类编程语言组成的混合结构。它比自然语言更精确,描述算法很简

    数组公式如何使用

    数组公式如何使用,计算,输入,数组,多列,数据,快速,  在excel中,要进行计算常用的是先设置第一行的公式,然后在采取下拉的方式来完成,如果同时要

    如何为Excel批量加前缀或后缀

    如何为Excel批量加前缀或后缀,后缀,批量,输入,前缀,选择,南京,  在使用Excel表格工作时,我们很经常接触输入相同的前缀或者后缀的情况。这些前

    php 删除数组重复的值

    php 删除数组重复的值,数组,函数,本文目录php 删除数组重复的值如何正确实现PHP删除数组重复元素PHP二维数组如何实现去除重复项php数组怎

    javascript对象怎么转换成字符串

    javascript对象怎么转换成字符串,字符串,参数,对象,序列化,属性,数组,在javascript中可以使用“JSON.stringify()”方法将对象转换成字符串,其语

    javascript如何获取字符串长度

    javascript如何获取字符串长度,字符,获取,属性,字符串长度,字符串,输出,javascript获取字符串长度的方法:1、使用length属性按字符来获取字符串

    php如何把一个数组倒序输出

    php如何把一个数组倒序输出,输出,数组,倒序,方法,循环,函数,PHP是一种流行的服务器端脚本语言,常用于Web开发。在PHP中,数组是一种非常常见的数据

    javascript中定义数组的方法有哪些

    javascript中定义数组的方法有哪些,数组,数组名,列表,元素,语句,方法,javascript中定义数组的方法:1、使用“var 数组名=[值列表]”语句;2、使用