一篇文章带你了解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 GetNext(string Tsub, vector<int>& Next)
{
    int j = 0, k = -1;
    Next[0] = k;
    while (j < Tsub.length() - 1)
    {
        if (k == -1 || Tsub[j] == Tsub[k])
        {
            Next[++j] = ++k;
        }
        else
        {
            k = Next[k];
        }
    }
}

步骤2：查找子串在母串中出现的位置。

//步骤2：
int KMP(string S, string T, vector<int> Next)
{
    int i = 0, j = 0;
    int m = S.length();
    int n = T.length();
    while (i < m && j < n)
    {
        if (j == -1 || S[i] == T[j])
        {
            i++;
            j++;
        }
        else
        {
            j = Next[j];
        }
    }
    if (j == n)
    {
        return i - j;
    }
    else
    {
        return -1;
    }
}

结合上面两个步骤写出完整代码：

#include <iostream>
#include <vector>
using namespace std;
//步骤1：
void GetNext(string Tsub, vector<int>& Next)
{
    int j = 0, k = -1;
    Next[0] = k;
    while (j < Tsub.length() - 1)
    {
        if (k == -1 || Tsub[j] == Tsub[k])
        {
            Next[++j] = ++k;
        }
        else
        {
            k = Next[k];
        }
    }
}
//步骤2：
int KMP(string S, string T, vector<int> Next)
{
    int i = 0, j = 0;
    int m = S.length();
    int n = T.length();
    while (i < m && j < n)
    {
        if (j == -1 || S[i] == T[j])
        {
            i++;
            j++;
        }
        else
        {
            j = Next[j];
        }
    }
    if (j == n)
    {
        return i - j;
    }
    else
    {
        return -1;
    }
}
int main()
{
    string S = "aaagoogleaaa";
    string T = "google";
    vector<int> Next(T.length());
    GetNext(T, Next);
    int retVal = KMP(S, T, Next);
    if (retVal == -1)
    {
        std::cout << "can't Index" << std::endl;
    }
    else
    {
        std::cout << "Index :" << retVal << std::endl;
    }
    return 0;
}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • C++ 匈牙利算法案例分析详解

    C++ 匈牙利算法案例分析详解

    匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名.匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法. -------等等,看得头大?那么请看下面的版本: 通过数代人的努力,你终于赶上了剩男剩女的大潮,假设你是一位光荣的新世纪媒人,在你的手上有N个剩男,M个剩女,每个人都可能对多名异性有好感(-_-||暂时不考虑特殊的性取向),如果一对男女互有好感,那么你就可以把这一对撮合在一起,现在

  • c++ 实现KMP算法

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

  • C/C++经典算法之约瑟夫问题详解

    C/C++经典算法之约瑟夫问题详解

    目录 什么是约瑟夫问题? 方法一:数组 方法二:环形链表 方法三:递归 总结 什么是约瑟夫问题? 约瑟夫问题:n个人围成一圈,初始编号从1~n排列,从约定编号为x的人开始报数,数到第m个人出圈,接着又从1开始报数,报到第m个数的人又退出圈,以此类推,最后圈内只剩下一个人,这个人就是赢家,求出赢家的编号. 是不是有点点复杂,其实该问题归结为模拟类型的算法题,根据题目要求模拟即可. 我说,一行代码解决约瑟夫问题! ???我去 别着急,我们一步一步学习 方法一:数组 在第一次遇到这个题的时候,我是用数

  • 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/C++实现快速排序算法的两种方式实例

    C/C++实现快速排序算法的两种方式实例

    目录 介绍 流程如下 实现 方式一 方式二 总结 介绍 快速排序是对冒泡排序算法的一种改进,快速排序算法通过多次比较和交换来实现排序. 流程如下 (图片来自百度) 实现 以下有两种实现方式,说是两种,其实就是在交换元素时具体细节上有点不同罢了. 方式一 int Partition(int A[],int low,int high){ int pivot=A[low];//第一个元素作为基准 while(low<high){ while(low<high && A[high]&g

  • 一篇文章带你了解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

  • 一篇文章带你使用Typescript封装一个Vue组件(简单易懂)

    一.搭建项目以及初始化配置 vue create ts_vue_btn 这里使用了vue CLI3自定义选择的服务,我选择了ts.stylus等工具.然后创建完项目之后,进入项目.使用快捷命令code .进入Vs code编辑器(如果没有code .,需要将编辑器的bin文件目录地址放到环境变量的path中).然后,我进入编辑器之后,进入设置工作区,随便设置一个参数,这里比如推荐设置字号,点下.这里是为了生成.vscode文件夹,里面有个json文件. 我们在开发项目的时候,项目文件夹内的文件很

  • 一篇文章带你搞定SpringBoot中的热部署devtools方法

    一.前期配置 创建项目时,需要加入 DevTools 依赖 二.测试使用 (1)建立 HelloController @RestController public class HelloController { @GetMapping("/hello") public String hello(){ return "hello devtools"; } } 对其进行修改:然后不用重新运行,重新构建即可:只加载变化的类 三.热部署的原理 Spring Boot 中热部

  • 一篇文章带你搞定SpringBoot不重启项目实现修改静态资源

    一.通过配置文件控制静态资源的热部署 在配置文件 application.properties 中添加: #表示从这个默认不触发重启的目录中除去static目录 spring.devtools.restart.exclude=classpath:/static/** 或者使用: #表示将static目录加入到修改资源会重启的目录中来 spring.devtools.restart.additional-paths=src/main/resource/static 此时对static 目录下的静态

  • 一篇文章带你解决 IDEA 每次新建项目 maven home directory 总是改变的问题

    Maven是基bai于项目对象模型,可以通du过一小段描述信息来管理zhi项目的构建,报告和文档的软件项dao目管理工具. 重装个系统,各种问题,idea 也出现各种问题 装了个新版的 idea 2020 2.x 版本的,不知道咋回事,其他都好使,就是创建 SpringBoot 项目时: 加载 pom.xml 总是出错,原因就是,新建立的项目 maven home directory 总是乱,没有安装 设置的默认方式 我试了,改当前项目的,不好使 该默认设置,不好使,网上的其他方法也试了,很奇怪

  • 一篇文章带你使用SpringBoot基于WebSocket的在线群聊实现

    一.添加依赖 加入前端需要用到的依赖: <dependency> <groupId>org.webjars</groupId> <artifactId>sockjs-client</artifactId> <version>1.1.2</version> </dependency> <dependency> <groupId>org.webjars</groupId> <

  • 一篇文章带你搞定 springsecurity基于数据库的认证(springsecurity整合mybatis)

    一.前期配置 1. 加入依赖 <dependency> <groupId>com.alibaba</groupId> <artifactId>druid-spring-boot-starter</artifactId> <version>1.1.10</version> </dependency> <dependency> <groupId>mysql</groupId> &

  • 一篇文章带你搞定Ubuntu中打开Pycharm总是卡顿崩溃

    由于 Ubuntu 中的汉字输入实在是太不友好了,所以装了个 搜狗输入法,好不容易把 搜狗输入法装好,本以为可以开开心心的搞代码了,然而... pycharm 一打开,就崩溃,关不掉,进程杀死还是不行,只能关机重启. 本以为 pycharm 出现了问题,又重装了两遍,还是不行. 最终发现竟然是搜狗输入法以及 fcitx 输入法的锅 唉,只能老老实实的把 fctix 和搜狗输入法卸载了: (1)Ubuntu 软件里卸载 fctix,然后将键盘输入法系统改成 IBus (2)卸载搜狗输入法 先查找软

  • 一篇文章带你搞懂Python类的相关知识

    一篇文章带你搞懂Python类的相关知识

    一.什么是类 类(class),作为代码的父亲,可以说它包裹了很多有趣的函数和方法以及变量,下面我们试着简单创建一个吧. 这样就算创建了我们的第一个类了.大家可以看到这里面有一个self,其实它指的就是类aa的实例.每个类中的函数只要你不是类函数或者静态函数你都得加上这个self,当然你也可以用其他的代替这个self,只不过这是python中的写法,就好比Java 中的this. 二.类的方法 1.静态方法,类方法,普通方法 类一般常用有三种方法,即为static method(静态方法),cl

  • 一篇文章带你了解Java中ThreadPool线程池

    一篇文章带你了解Java中ThreadPool线程池

    目录 ThreadPool 线程池的优势 线程池的特点 1 线程池的方法 (1) newFixedThreadPool (2) newSingleThreadExecutor (3) newScheduledThreadPool (4) newCachedThreadPool 2 线程池底层原理 3 线程池策略及分析 拒绝策略 如何设置maximumPoolSize大小 ThreadPool 线程池的优势 线程池做的工作主要是控制运行的线程数量,处理过程中将任务放入队列,然后在线程创建后启动这些

随机推荐