28. 找出字符串中第一个匹配项的下标

这篇具有很好参考价值的文章主要介绍了28. 找出字符串中第一个匹配项的下标。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

28. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。文章来源地址https://www.toymoban.com/news/detail-689091.html

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.size()==0){
            return 0;
        }
        int length1=haystack.size();
        int length2=needle.size();
        vector<int> next(needle.size());
        //初始化
        next[0]=0;
        int j=0;//前缀的末尾位置,同时也是前后缀相同元素的个数
        int i=1;//后缀的末尾位置
        for(int i=1;i<needle.size();i++){
            while(needle[j]!=needle[i] && j>0){
                j=next[j-1];
            }
            if(needle[j]==needle[i]){
                j++;
            }
            next[i]=j;
        }
        j=0;
        for(int i=0;i<haystack.size();i++){
            while(j>0 && haystack[i]!=needle[j]){
                j=next[j-1];
            }
            if(haystack[i]==needle[j]){
                j++;
            }
            if(j==needle.size()){
                return (i-needle.size()+1);
            }
        }
        
        return -1;
        
    }
};

到了这里,关于28. 找出字符串中第一个匹配项的下标的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode的AC指南 —— 字符串/KMP:28.找出字符串中第一个匹配项的下标

    摘要: Leetcode的AC指南 —— 字符串/KMP:28.找出字符串中第一个匹配项的下标 。题目介绍:给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。 题目介绍 :给你两

    2024年02月02日
    浏览(55)
  • Leecode找出字符串中第一个匹配项的下标 即实现strSTR()函数

    目录 简单介绍该函数的作用         在我们去用查找微信或者qq聊天记录的时候,我们总不能一句一句去找吧。我们需要用到的功能底层大概是此博客所讲的这个函数熬。 一.算法需要传入的参数和返回类型         需要传入的就是和所有的文本,返回的是当前

    2024年02月12日
    浏览(56)
  • 【LeetCode】每日一题&&两数之和&&寻找正序数组的中位数&&找出字符串中第一个匹配项的下标&&在排序数组中查找元素的第一个和最后一个位置

    ========================================================================= 主页点击直达: 个人主页 我的小仓库: 代码仓库 C语言偷着笑: C语言专栏 数据结构挨打小记: 初阶数据结构专栏 Linux被操作记: Linux专栏 LeetCode刷题掉发记: LeetCode刷题 算法: 算法专栏  C++头疼记: C++专栏 计算机

    2024年02月08日
    浏览(52)
  • [C][整理][数组]从键盘输入一个字符串(其长度小于20),找出其中ASCII码值最小的字符,并输出该字符。

    题目:从键盘输入一个字符串(其长度小于20),找出其中ASCII码值最小的字符,并输出该字符。 只允许在 /***Program***/ 与 /***End***/ 之间添加。 测试输入:kdjhfkbe 测试输出:b 该程序的主要步骤是读取用户输入的字符串、遍历字符串中的每个字符,找到ASCII码值最小的字符并输出

    2024年02月06日
    浏览(76)
  • sqlserver 查找某个字符在字符串中第N次出现的位置

    如果想要在 Microsoft SQL Server 中查找某个字符在字符串中第 N 次出现的位置,可以使用 CHARINDEX 函数。该函数接受三个参数: 要查找的字符(必需) 要搜索的字符串(必需) 开始搜索的位置(可选) 它会返回所查找字符在字符串中的位置,如果字符不存在,则返回 0。 举个例子,如果

    2024年02月13日
    浏览(37)
  • 【字符串匹配】暴力匹配算法

    ​ 暴力匹配算法,也称为朴素字符串匹配算法,是一种简单但不高效的字符串匹配方法。它的原理非常直观,其主要思想是逐个字符地比较文本串和模式串,从文本串的每个可能的起始位置开始,依次检查是否有匹配的子串。以下是暴力匹配算法的详细原理: 1. 一个字一个

    2024年02月09日
    浏览(51)
  • 【数据结构】数组和字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)

      字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列,简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作: S = ′ ′ a 0 a 1 … a n − 1 ′ ′ S=\\\'\\\'a_{0} a_{1}…a_{n-1}\\\'\\\' S = ′′ a 0 ​ a 1 ​ … a n − 1 ′′ ​   其中S是串名,引号中

    2024年02月05日
    浏览(72)
  • 字符串查找匹配算法

    字符串匹配(查找)是字符串的一种基本操作:给定带匹配查询的文本串S和目标子串T,T也叫做模式串。在文本S中找到一个和模式T相符的子字符串,并返回该子字符串在文本中的位置。 Brute Force Algorithm,也叫朴素字符串匹配算法,Naive String Matching Algorithm。 基本思路就是将

    2024年02月14日
    浏览(55)
  • python字符串模糊匹配,并计算匹配分数

    thefuzz包以前叫fuzzywuzzy,0.19版本开始改名为thefuzz,github地址: GitHub - seatgeek/thefuzz: Fuzzy String Matching in Python 可以通过命令pip install thefuzz安装此包。用法还是比较简单的: 上面两个字符串的相似度为89%。 我们先看看这个包下面的源码,来查看thefuzz是怎么实现模糊匹配的。the

    2023年04月23日
    浏览(103)
  • 字符串匹配算法:KMP

    Knuth–Morris–Pratt(KMP)是由三位数学家克努斯、莫里斯、普拉特同时发现,所有人们用三个人的名字来称呼这种算法,KMP是一种改进的字符串匹配算法,它的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。它的时间复杂度是 O(m+n) 字

    2024年02月06日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包