当前位置: 首页 > article >正文

代码随想录-字符串-实现strStr()--KMP

题目描述

思路:典型的数据结构中的KMP算法实现

代码与解析

假设两个字符串长度分别为m和n,暴力解则为O(m*n)

引入KMP算法降低时间复杂度,求next数组是O(m) 遍历匹配串是O(n)

KMP关键思路

①求出模式串的next数组,即最长公共前后缀的长度。前缀定义,不含最后一个字母,后缀定义不含第一个字母。

next[i] 代表第i个位置的最长公共前后缀的长度

这里定义next[0]=0,即第一个字母的最长公共前后缀长度都是0

遍历模式串

j代表模式串中i位置的最长前后缀长度为j,所以不配的时候回退为next[j-1]

private static 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;
            }
        }

模式串与匹配串

public static int strStr(String haystack, String needle) {
            if (needle.isEmpty()) 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;
}

整体KMP代码

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty())
            return 0;
        // 字符串的模式匹配
        int length = needle.length();
        int[] next = new int[length];
        getNext(next, needle);
        // System.out.println(Arrays.toString(next));
        int j = 0;
        // j 来对子串操作 i来操作匹配串
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            //模式串到头了,j应该是最后一个字符之后又加一了,所以j==length,而不是length-1
            if(j == length){
                return i-length+1;
            }
        }
        return -1;
    }

    // 构建next数组,用kmp算法实现此功能
    private void getNext(int[] next, String needle) {
        int j = 0;// 最长相等前后缀长度 不算第一个和最后一个字母,所以对于第一个位置,公共长度是0
        next[0] = j;
        for (int i = 1; i < next.length; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                // 其实这里比较的是i和j都向公共前后缀子串后移动了一个之后的位置
                // 不相等,回退 j是公共长度,所以应该回退到 next[j-1] 这个之前的是可能相交的公共子串部分
                j = next[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }
}


http://www.kler.cn/a/383464.html

相关文章:

  • EsChatPro 接入国内 DeepSeek 大模型
  • Issac ROS navigation测试
  • Linux网络——网络基础
  • 解析mysqlbinlog
  • 如何根据一系列提交文件,匹配对应的git提交记录?用ai
  • CNN回归-卷积神经网络(Convolutional Neural Network)
  • qgis加载获取远程wms数据失败
  • 【C++篇】无序中的法则:探索 STL之unordered_map 与 unordered_set容器的哈希美学
  • php Rides 存入list类型,然后拿2000条,后去除Rides2000条
  • SpringBoot整合Freemarker(二)
  • PHP反射API与面向对象编程:当“魔镜”遇上“家族聚会”
  • 域迁移相关数据集生成脚本
  • sql纵表转横表
  • WPF界面控件Essential Studio for WPF更新至2024 v3,具有更高性能 | 附下载
  • 看电动缸是如何提高农机的自动化水平
  • SQL 专项练习题(合集)
  • 《通过 Jmeter 压测存储过程详解》
  • Gitlab-执行器为Kubetnetes时的注意事项,解决DNS解析问题
  • 基于ExtendSim的库存与订购实验
  • spring-data-jpa 一对多,多对一,多对多
  • PathVariable annotation was empty on param 0.问题解决
  • 《C语言程序设计现代方法》note-3 选择语句 循环语句
  • C++(一)
  • 开学轻松逆袭孩子的学习利器培养自律习惯,提高学习效率❗❗让习惯养成更轻松~
  • 【Rust Crate之Actix Web(一)】
  • Sigrity Power SI 3D-EM Inductance Extraction模式如何进行电感的提取操作指导(一)