Leetcode28 Java实现_雷金的博客-程序员宅基地

Leetcode28 Java实现

在这里插入图片描述

代码实现（kmp）

class Solution {
    public int strStr(String haystack, String needle) {
        
       
        if(needle.length()<1){
            return 0;
        }
       
        char[] ha = haystack.toCharArray();
        char[] ne = needle.toCharArray();
        int hi=0;
        int ni = 0;
        int [] next = getNextArray(ne);
        while(hi<ha.length&&ni<ne.length){
            if(ha[hi]==ne[ni]){
                hi++;
                ni++;
            }else{ if(next[ni]==-1){
                hi++;
            }else{
                ni=next[ni];
            }
                 }
        }
        return ni==ne.length? hi-ni:-1; 
    }
    public static int [] getNextArray(char[] a){
        if(a.length==1){
            return new int[] {-1};
        }
        int []next = new int[a.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int j = 0;
        while(i<next.length){
            if(a[i-1]==a[j]){
                next[i++]=++j;
            }else if(j>0){
                j=next[j];
            }else{
                next[i++]=0;
            }
        }
        return next;
    }
}

本文链接：https://blog.csdn.net/weixin_43780574/article/details/84397763

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

MySql的坑-程序员宅基地

这是本人装完MySQL 8.X的数据库之后遇到的坑：报错如下：后来经查资料，是因为8.0版本之后的时区相差8个小时处理办法就是：在连接后面加上&serverTimezone=GMT%2B8如下：..._mysql的坑

Linux中KDE桌面环境使用Deepin-Wine软件方法_arch kde 换成 deppin桌面-程序员宅基地

环境Ubuntu 18.04 bionicKDE 5.47.0 / Plasma 5.12.7描述在非gnome桌面环境下，Deepin-Wine软件大部分不能启动，例如deepin-Tim，deepin-QQ以及微信等。按照DLM的说法，深度在打包Deepin-Wine软件时加入了对Gnome的依赖。通过安装gnome-settings-daemon即可解决。安装gnome-se..._arch kde 换成 deppin桌面

python学习笔记（Tkinter编程利用Treeview实现表格自动更新）-程序员宅基地

博主今天总结这段时间抽空写的一个GUI编程项目功能是查看本地打印机队列，可选择指定队列重新打印直接上图UI设计包括3个区域左上方，右上方和下方列表区域使用网格grid方法来分配位置下面是界面设计的代码 1 #!/usr/bin/env python 2 # -*- coding: utf-8 -*- 3 4 from Tkinter impor...

老生常谈，HashMap的死循环-程序员宅基地

占小狼转载请注明原创出处，谢谢！问题最近的几次面试中，我都问了是否了解HashMap在并发使用时可能发生死循环，导致cpu100%，结果让我很意外，都表示不知道有这样的问题，让我意外的是面试者的工作年限都不短。由于HashMap并非是线程安全的，所以在高并发的情况下必然会出现问题，这是一个普遍的问题，虽然网上分析的文章很多，还是觉得有必须写一篇文章，让关注我公众号的同学能够意识到这个...

数据摄取-程序员宅基地

　　Amazon Kinesis：大规模数据流的实时处理; 　　Apache Chukwa：数据采集系统; 　　Apache Flume：管理大量日志数据的服务; 　　Apache Kafka：分布式发布-订阅消息系统; 　　Apache Sqoop：在Hadoop和结构化的数据存储区...

ArrayList和Arrays.ArrayList-程序员宅基地

java中的ArrayList内部是由数组实现的，但是正因为这一点，ArrayList与数组打交道的时候应该要注意一些问题。测试代码1public static void main(String[] args) { //创建一个字符串数组 String[] words = "And that is how we know the Earth to be bana..._arrays.arraylis