首页 > 编程语言 >KMP算法的两种实现形式

KMP算法的两种实现形式

时间:2024-08-12 20:53:03浏览次数:15  
标签:两种 charAt int needle length next 算法 KMP haystack

以leetcode 28.实现strStr()为例:

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回  -1 

示例 1:

输入:haystack = "sadbutsad", needle = "sad"
输出:0
解释:"sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。

示例 2:

输入:haystack = "leetcode", needle = "leeto"
输出:-1
解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。

提示:

  • 1 <= haystack.length, needle.length <= 104
  • haystack 和 needle 仅由小写英文字符组成

方式一:前缀和数组统一减一

这个方式下,模式串匹配失败的回退方式是从本身位置,获取回退位置

class Solution {
    public void getNext(int[] next, String s){
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++){
            while(j >= 0 && s.charAt(i) != s.charAt(j+1)){
                j=next[j];
            }

            if(s.charAt(i) == s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }

        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for(int i = 0; i < haystack.length(); i++){
            while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
                j = next[j];
            }
            if(haystack.charAt(i) == needle.charAt(j+1)){
                j++;
            }
            if(j == needle.length()-1){
                return (i-needle.length()+1);
            }
        }

        return -1;
    }
}

方式二:前缀和数组不减一

这个方式下,模式串匹配失败的回退方式是从本身位置的前一个位置处,获取回退位置 

class Solution {
    //前缀表(不减一)Java实现
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) 
                j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;

    }
    
    private void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) 
                j = next[j - 1];
            if (s.charAt(j) == s.charAt(i)) 
                j++;
            next[i] = j; 
        }
    }
}

 

标签:两种,charAt,int,needle,length,next,算法,KMP,haystack
From: https://blog.csdn.net/m0_74051652/article/details/141141806

相关文章

  • 排序算法之总述
    title:排序算法date:2024-7-1815:20:07+0800categories:汇总tags:排序算法时间复杂度汇总description:排序算法(sortingalgorithm)用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用,因为有序数据通常能够被更高效地查找、分析和处理。math:true排......
  • 排序算法之桶排序
    title:桶排序date:2024-7-2518:58:19+0800categories:排序算法tags:排序算法桶排序description:桶排序(bucketsort)是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶,每个桶对应一个数据范围,将数据平均分配到各个桶中;然后,在每个桶内部分别执行排序;最终按......
  • 排序算法之归并排序
    title:归并排序date:2024-7-1915:03:06+0800categories:排序算法tags:排序算法归并排序description:归并排序(MergeSort)是一种基于分治法的有效排序算法。它将一个列表分成较小的子列表,对每个子列表进行排序,然后合并这些子列表以产生一个有序列表。math:true......
  • NDT算法详解与C++实现
    点云匹配在感知环节是一个很重要的信息获取手段,而其中的算法也有几个比较经典了,例如ICP(IterativeClosestPoint,迭代最近点)算法,而本文决定记录学习的是NDT算法,也就是NormalDistributionTransform,正态分布变换算法。什么是正态分布变换算法呢,简言之,就是把空间中的点云进行整......
  • 2024华为OD笔试机试 - 模拟目录管理功能 (python/c++/java D卷C卷真题算法)
    华为OD机试(C卷+D卷)2024真题目录(Java&c++&python)题目描述实现一个模拟目录管理功能的软件,输入一个命令序列,输出最后一条命令运行结果。支持命令:创建目录命令:mkdir目录名称,如mkdirabc为在当前目录创建abc目录,如果已存在同名目录则不执行任何操作。此命令无输出......
  • 6-61 顺序表基本运算算法的实现
    线性表实验一实现顺序表各种基本运算的算法目的:领会顺序表存储结构和掌握顺序表中各种基本运算算法设计。内容:编写程序,实现顺序表的各种基本运算算法(假设顺序表的元素类型ElemType为char),并在此基础上设计一个主程序,完成如下功能:(1)初始化顺序表L。(2)依次插入a、b......
  • 盘点两种方法来判断一个列表里面,按关键词进行筛选,留下包含有关键词的论文题目
    大家好,我是Python进阶者。前言前几天才哥群里有个粉丝提问,忘记是谁了,过去有段时间,当时没来得及截图,不知道谁问的了,不过题目当时记下来了,如下图所示。看上去并不是很难的样子,这个示例代码,看上去逻辑什么的也没有问题,但是结果输出就是有些不对。究其原因,因为title里边是列表,而不......
  • 「代码随想录算法训练营」第三十五天 | 动态规划 part8
    121.买卖股票的最佳时机题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/文章讲解:https://programmercarl.com/0121.买卖股票的最佳时机.html题目难度:简单视频讲解:https://www.bilibili.com/video/BV1Xe4y1u77q题目状态:有一半的思路思路一:贪心对......
  • 足球比赛结果预测系统:遗传算法的研究
    引言最近有个朋友时运不济,自己胡乱玩被足球预测的推子骗了一回又一回,明明我就是专门做足球预测的,偏偏不信我还赌气说自己有本事一个人也能成,现在隔得跟个小怨妇似得,觍着脸回来找我要我传他心得,没办法,好歹十几年的兄弟,他再怎么发病也只能原谅他了,于是就有了这篇文章。不过足球......
  • 【算法学习】排序算法汇总
    冒泡排序1、冒泡排序简介冒泡排序的英文BubbleSort,是一种最基础的交换排序。之所以叫做冒泡排序,因为每一个元素都可以像小气泡一样,根据自身大小一点一点向数组的一侧移动冒泡排序的原理:冒泡轮数:每一轮只能将该轮中最大的数排至最后面。即第一轮只能确定将末位上的数归位......