leetcode最长回文子串_kmp算法题

leetcode最长回文子串_kmp算法题实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。示例 1:输入: haystack = “hello”, needle = “ll”输出: 2示例 2:输入: haystack = “aaaaa”, needle = “bba”输出: -1说明:当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

题解

  1. kmp算法
class Solution { 
   
public:
    void getNext(string needle,vector<int>&next){ 
   
        next[0] = -1;
        int i = -1,k = 0;
        while(k < needle.size() - 1){ 
   
            while(i != -1 && needle[k] != needle[i])i = next[i];
            if(i == -1 || needle[i] == needle[k]){ 
   
                next[++ k] = ++ i;
            }
        }
    }
    int strStr(string haystack, string needle) { 
   
        if(needle == "")return 0;
        vector<int>next(needle.size());
        getNext(needle,next);
        for(int i = 0;i < next.size();i ++){ 
   
            cout<<next[i]<<endl;
        }
        int j = 0;
        for(int i = 0;i < haystack.size();i ++){ 
   
            while(j != -1 && needle[j] != haystack[i])j = next[j];
            j ++;
            if(j == needle.size())return i - needle.size() + 1;
        }
        return -1;
    }   
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169163.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 5G nr频段_5g哪个信道信号强

    5G nr频段_5g哪个信道信号强文章目录1.工作频段2.基站信道带宽2.1传输带宽配置2.2最小保护带3.信道安排3.1信道栅格3.2同步栅格参考文献1.工作频段NR工作在两大频率范围(FrequencyRange,FR):FR1和FR2,如下表1-1所示[1]。表1-1.频率范围的定义[1](TS38.104Table5.1-1)FR1和FR2中,又划分了多个不同的工作频段,如下表1-2和下表1-3所示[1]。表中的n代表NR。表1-2.NR在FR1中的工作频段[1](TS38

  • php 动静分离原理,nginx动静分离的好处

    php 动静分离原理,nginx动静分离的好处动静分离是将网站静态资源(HTML,JavaScript,CSS,img等文件)与后台应用分开部署,提高用户访问静态代码的速度,降低对后台应用访问。动静分离的一种做法是将静态资源部署在nginx上,后台项目部署到应用服务器上,根据一定规则静态资源的请求全部请求nginx服务器,达到动静分离的目标。nginx动静分离的好处api接口服务化:动静分离之后,后端应用更为服务化,只需要通过提供api接口即…

  • idea插件开发指南_idea get set插件

    idea插件开发指南_idea get set插件gitee地址:https://gitee.com/jyq_18792721831/studyplugin.gitidea插件开发入门idea插件开发–配置idea插件开发–服务-翻译插件idea插件开发–组件–编程久坐提醒介绍组件应用程序启动项目打开模块打开应用程序/项目关闭监听程序代码中注册监听器声明注册监听器项目级的监听器声明注册的其他配置自定义监听器接口消息系统设计主题消息总线连接广播嵌套消息组件定义应用程序级别项目级别监听器定义Java计时器实例需求分解项目创建配置界面存储服务配置和

  • gridlayout布局

    gridlayout布局浅谈android4.0开发之GridLayout布局分类: Android应用开发技巧2012-03-1123:51 3646人阅读 评论(1) 收藏 举报androidlayoutbuttonencoding框架编程作者:李响         本文重点讲述了自android4.0版本后新增的GridLayout网格布局的一些基本

  • C++优先队列_队列queue中添加元素的方法

    C++优先队列_队列queue中添加元素的方法1.优先级队列(priority_queue)1.1基本概念之前已经提到了队列(queue),队列是一种先进先出(FirstinFirstout,FIFO)的数据类型。每次元素的入队都只能添加到队列尾部,出队时从队列头部开始出。优先级队列(priority_queue)其实,不满足先进先出的条件,更像是数据类型中的“堆”。优先级队列每次出队的元素是队列中优先级最高的那个元素,而不是队首的元素。这个优先级可以通过元素的大小等进行定义。比如定义元素越大优先级越高,那么每次出队,都是将当前队.

  • 【Java入门练习100例】07.各数字的和——取余运算

    【Java入门练习100例】07.各数字的和——取余运算除法运算取余运算

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号