首页 > 编程语言 >LeetCode_0028. 找出字符串第一个匹配项的下标,KMP算法的实现

LeetCode_0028. 找出字符串第一个匹配项的下标,KMP算法的实现

时间:2024-09-03 16:14:58浏览次数:12  
标签:匹配 nextval 0028 needle next KMP 下标 haystack LeetCode

题目描述

  给你两个字符串 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 仅由小写英文字符组成
    

KMP算法

  字符串匹配问题,设主串有m个字符,模式串有n个字符,暴力方法要时间O(mn)。KMP算法通过求解next数组,消除了失配时主串回溯步骤,使得时间复杂度降低到O(m+n)。

核心 —— next/nextval数组

  当haystack[p]和needle[q]失配发生时,主串指针p不动,模式串指针q跳转到nextval[q]与主串匹配。

分析模式串,求解next/nextval数组

  • 先求next数组

    next[i] = needle[0..i]的最长匹配前后缀的长度;

  • 推导nextval数组

    nextval[0] = -1;
    nextval[i] = next[i-1];

  • 也可以一步到位,比如这个实现

    vector<int> nextval(n, 0);
    nextval[0] = -1;      // -1表示下一匹配中,主串指针p++, 模式串指针q=0
    for(int j = 0, k = -1; j < n - 1; ) {
      if(k == -1 || needle[j] == needle[k]) {
        ++k, ++j;
        nextval[j] = k;
      } else {
        k = next[k];      // point
      }
    }
    

匹配,返回第一次匹配模式串的下标

    int p = 0, q = 0;
    while(q < n && p < m) {
      if(haystack[p] == needle[q]) {
        ++p, ++q;
      } else {
        if(nextval[q] == -1) {
          ++p;
          q = 0;
        } else {
          q = nextval[q];
        }
      }
    }

    if(q == n) {
      return p - n;
    } else {
      return -1;
    }

标签:匹配,nextval,0028,needle,next,KMP,下标,haystack,LeetCode
From: https://www.cnblogs.com/GaogaoBlog/p/18394816

相关文章

  • 代码随想录算法训练营|Day01 LeetCode 704.二分查找,27.移除元素,977.有序数组的平方
    数组理论基础数组是存放在连续空间上的相同类型数据的集合数组的元素是不能删的,只能覆盖704.二分查找LeetCode:704.有序数组的平方classSolution{public:intsearch(vector<int>&nums,inttarget){intlength=nums.size();inti=0......
  • Java LeetCode练习
        LeetCodeExercise        807.保持城市天际线    题解:贪心        从左侧和右侧看,城市天际线等于矩阵grid的每一行的建筑物高度最大值;从顶部和底部看,城市天际线等于矩阵grid的每一列的建筑物高度最大值。只要不改变每一行和每一列......
  • 1049. 最后一块石头的重量 II(leetcode)
    https://leetcode.cn/problems/last-stone-weight-ii/description/思路较为巧妙的dp题,关键点在于如何将问题转化为01背包,有点贪心的思想主要是划分为两堆尽可能相等的石碓,然后判断能否凑出这个偏小的石碓(若干石头中选,能否选出这个价值)这里根据f[i]的定义可以有两种做法,1.f......
  • 扩展KMP (ex_KMP)
    一些约定:字符串下标从1开始s[1,i]表示S的第一个到第i个字符组成的字符串解决的题型:给你两个字符串A,B(A.size()=n,B.size()=m),求p数组p[i]表示最大的len使得A[i,i+len-1]=B[1,len]即A的第i位与B前缀的最大匹配的长度比如;A:aaaabaaB:aaaap数组就是{4321021}算......
  • Leetcode——1.合并有序数组
    给你两个按非递减顺序排列的整数数组nums1_和nums2,另有两个整数m和n,分别表示nums1和nums2中的元素数目。请你合并nums2_到nums1中,使合并后的数组同样按非递减顺序排列。注意:最终,合并后数组不应由函数返回,而是存储在数组nums1中。为了应对这种情况,nums1的初......
  • 每日一题:Leetcode-224 基本计算器
    力扣题目解题思路java代码力扣题目:给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval() 。示例1:输入:s="1+1"输出:2示例2:输入:s="2-1+2"输出:3示例3:输入:s......
  • 【LeetCode】两数之和
    题目:在数组中找到2个数之和等于给定值的数字,结果返回2个数字在数组中的下标。要求时间复杂度为 O(n)。解题分析:作者:halfrost链接:https://leetcode.cn/leetbook/read/leetcode-cookbook/5lu4og/顺序扫描数组,对每一个元素,在map中找能组合给定值的另一半数字,如果找......
  • Leetcode37-和相等的子数组(2395)
    1、题目给你一个下标从0开始的整数数组nums,判断是否存在两个长度为2的子数组且它们的和相等。注意,这两个子数组起始位置的下标必须不相同。如果这样的子数组存在,请返回true,否则返回false。子数组是一个数组中一段连续非空的元素组成的序列。示例1:输入......
  • leetcode 75. Sort Colors & 三路快速排序
    leetcode75.SortColors&三路快速排序只有0和1的情况在这种简化情况下,我们只需要顺序遍历数组,遇到0就放到前面即可。classlocalExperiment{public:voidsort01(std::vector<int>&nums){intzero_ptr=0;for(inti=0;i<nums.size();......
  • 二叉树的直径(LeetCode)
    题目给你一棵二叉树的根节点,返回该树的 直径 。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。解题classTreeNode:def__init__(self,val=0,left=......