首页 > 编程语言 >kmp算法详解

kmp算法详解

时间:2023-05-10 18:24:01浏览次数:58  
标签:匹配 int 模式 next 算法 详解 kmp 下标

相关题目链接:LeetCode 28. 找出字符串中第一个匹配项的下标

代码如下


func strStr(s string, p string) int {
    //kmp算法,下标一般从1开始,
    //next数组表示的是最长相等前后缀的长度,也就是最少移动几位,使得前后缀相等,
    // s是主串,p是模式串
    n:=len(s)
    m:=len(p)
    s = " " +s 
    p = " "+ p 
    next:=make([]int,m+1)
    //求next数组的过程,其实也是一个匹配的过程,也就是相当于自己和 错一位的自己匹配
    for i,j:=2,0;i<=m;i++{  
        for j>0 && p[i] != p[j+1]{  
            j = next[j]
        }
        if p[i] == p[j+1]{
            j++
        }
        next[i] = j  //记录下当前的匹配值
    }

    //匹配过程  ,主串 下标从1 开始,模式串下标从0开始
    for i,j:=1,0;i <=n;i++{
        for j>0 && s[i] != p[j+1]{  //只要模式串的指针不在起始位置,同时 主串 与 模式串 不匹配,则回退到next[j] 的位置
            j = next[j]
        }
        if s[i] == p[j+1] {  //如果匹配了,那就进行下一个匹配
            j++
        }
        if j== m{  //如果已经匹配到最后了,匹配成功,
            return i-m
        }
    }
    return -1





}

求next数组的代码模板:

// s[]是长文本,p[]是模式串,n是s的长度,m是p的长度
求模式串的Next数组:
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

标签:匹配,int,模式,next,算法,详解,kmp,下标
From: https://www.cnblogs.com/lxing-go/p/17388507.html

相关文章

  • TFIDF算法java实现
     一、算法简介       TF-IDF(termfrequency–inversedocumentfrequency)。       TFIDF的主要思想是:如果某个词或短语在一篇文章中出现的频率TF高,并且在其他文章中很少出现,则认为此词或者短语具有很好的类别区分能力,适合用来分类。TFIDF实际上是:TF*IDF,TF词频(Ter......
  • MarkDown语法基础详解附带视频链接
    MarkDown语法基础大家如果喜欢的话就收藏或者分享给你的小伙伴把!以下总结的为常见语法,我使用的是Typora破解版,里面有快捷键,讲语法是为了让大家更好的理解大家也可以去看详细视频讲解基础篇视频讲解链接画图篇视频讲解链接标题标题使用方法:#+空格+标题(回车得到标题)标题分为......
  • 万字长文详解如何使用Swift提高代码质量
    前言京喜APP最早在2019年引入了Swift,使用Swift完成了第一个订单模块的开发。之后一年多我们持续在团队/公司内部推广和普及Swift,目前Swift已经支撑了70%+以上的业务。通过使用Swift提高了团队内同学的开发效率,同时也带来了质量的提升,目前来自Swift的Crash的占比不到1%。在这过程......
  • 永磁同步电机的控制算法仿真模型: 1. 永磁同步电机的MRAS无传感器矢量
    永磁同步电机的控制算法仿真模型:1.永磁同步电机的MRAS无传感器矢量控制:2.永磁同步电机的SMO无传感器矢量控制(反正切+锁相环);3.永磁同步电机DTC直接转矩控制;4.永磁同步电机的有传感器矢量控制;5.永磁同步电机的位置控制YID:92128687292912454......
  • 异步电机有速度传感器矢量控制算法的C代码+仿真模型,仿真采用C代码直接在Simulink模型
    异步电机有速度传感器矢量控制算法的C代码+仿真模型,仿真采用C代码直接在Simulink模型里进行仿真的方式,当你不具备硬件调试的条件时,可以通过这种方法直接对代码进行仿真验证,所见即所得!采用双闭环解耦控制算法,转速外环电流内环,转矩与励磁解耦控制,SVPWM空间电压矢量调制,电流谐波很小,......
  • Vue插槽详解
    vue插槽的作用Vue插槽是Vue中常见的一种组件间的相互通信方式,作用是让父组件可以向子组件指定位置插入html结构,适用于父组件===>子组件,在要接收数据的组件页面通过<slot></slot>标签来表示,简单来说,就是通过此标签来起到占位的作用,而要插入的内容也会对应到标签所在的位置。1.默......
  • 正则表达式详解
    一、正则表达式概述正则表达式是一组由字母和符号组成的特殊文本,它可以用来从文本中找出满足你想要的格式的句子。通俗的讲就是按照某种规则去匹配符合条件的字符串一个正则表达式是一种从左到右匹配主体字符串的模式。“Regularexpression”这个词比较拗口,我们常使用缩写......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素。第一章 数组part01
    今天开始第一天,其实之前也刷过题,也写过博客,可是没有坚持下去;主要是没有动力吧,我又是一个严重的拖延症患者,还好遇到刷到Carl哥的视频,记得是在bilibili分享的二分法视频,感觉讲的挺好的,就加了微信;然后发现有刷题训练营,太适合我这种人了,果断加入,哈哈,废话不多说,开始刷题。  第......
  • 基于一阶RC模型,电池带遗忘因子递推最小二乘法+扩展卡尔曼滤波算法(FFRLS+ EKF),参数与SOC
    基于一阶RC模型,电池带遗忘因子递推最小二乘法+扩展卡尔曼滤波算法(FFRLS+EKF),参数与SOC的在线联合估计,matlab程序YID:76100659957301925......
  • 基于二阶RC模型锂电池扩展卡尔曼+无迹卡尔曼滤波算法联合估计EKF-UKF,其中EKF在线辩识
    基于二阶RC模型锂电池扩展卡尔曼+无迹卡尔曼滤波算法联合估计EKF-UKF,其中EKF在线辩识所有模型参数欧姆内阻,极化电阻电容,UKF估计soc,循环递推matlab脚本程序sci参考文献ID:26349673074081614......