一文理解kmp算法(java代码)

简介: 一文理解kmp算法(java代码)

kmp是为了解决什么问题?


字符串匹配问题,用来在主字符串中查找匹配字符串的位置


N, M :字符串的长度char s[N], p[M]:待匹配串 匹配串eg: s[N] = “ababa”, p[M] = “aba”判断 s[N] 中是否有p[M]这个子串,如果有,开始下标为多少?

解决方法


暴力算法


   for(int i = 1; i <= n; i++) {
    bool flag = true;
    for(int j = 1; j <= m;j++) {
        if(s[i+j-1] != p[j]) {
            flag = false;
            break;
         }         
      }
   }


时间复杂度:O(n*m)


kmp优化


对于模式串中已经匹配过的那些字符,如果我们能找到一些规律,将模式串多往后移动几位,而不是像暴力算法算法一样,每次把模式串移动一位,就可以提高算法的效率。kmp算法给我们提供的思路是:对于模式串,将每一个字符在匹配失败时可以向后移动的最大距离保存在一个next数组。这样当匹配失败时就可以按照next数组中保存的数字向后多移动几位。从而提高算法的效率。


在讲述之前,我们先摆出两个概念:


前缀:指的是字符串的子串中从原串最前面开始的子串,如abcdef的前缀有:a,ab,abc,abcd,abcde

后缀:指的是字符串的子串中在原串结尾处结尾的子串,如abcdef的后缀有:f,ef,def,cdef,bcdef

什么是前缀数组next[]

在KMP算法中有个关键的数组,叫做前缀数组,每一个子串有一个固定的next数组,它记录着字符串匹配过程中失败情况下可以向后多跳几个字符,其实也是子串的前缀和后缀相同的最长长度。



怎么求这个数组我们放在最后说,先说怎么使用这个前缀数组来实现kmp算法


算法思路


思路其实已经说过了,就是在暴力的算法的基础上,在匹配失败的时候往后多跳几位,而跳几位保存在前缀数组中。接下来我们看一下原理是什么样的,为什么前缀数组就可以作为跳几步的依据。举个例子,下图中已经写好了总串s和模式串p,模式串的前缀数组为[0,0,1,2,3],且所以下标都是从1开始。看图中当i=8,j=4时s[i] != p[j + 1],即将要匹配失败了,图中红色圈住的是子串的后缀。黄圈圈住的是前缀。蓝色圈圈住的是已经和后缀匹配过的部分,那么下一次将模式串后移prefix[j]=2位时,原来的前缀正好对着蓝色圈圈部分,因为前缀=后缀=蓝色圈圈部分,所以移动后的橙色部分就不用再判断了。


再用上一个双指针算法思路。i遍历总串s,j遍历模式串p,判断s[i] 和 p[j + 1]是否匹配。不匹配就将j重置为前缀数组中prefix[j]的值。匹配的话j忘后移动一位。当匹配了n个字符后即代表完全匹配。此时答案即为i-n,如果要继续搜索,要将j再置为prefix[j]。


为了方便写代码所有数组的下标都从1开始


// kmp匹配
for (int i = 1, j = 0; i <= m; i++) {
    while (j != 0 && s[i] != p[j + 1]) {
        j = prefix[j]; // s[i] != p[j + 1]即不匹配,则往后移动
    }
    if (s[i] == p[j + 1])
        j++; // 匹配时将j++进行下一个字符的匹配
    if (j == n) { 
        j = prefix[j]; // 完全匹配后继续搜索
        System.out.print(i - n + " ");
    }
}


怎么求前缀数组


前缀数组是kmp里面最难的部分,网上也有很多种求法。比如利用后一个元素和前面的元素之间存在数学公式关系来求,我们这里使用的方式是和上面的匹配过程类似的方法,也就是将前缀看作模式串,在p中匹配他。也就是字符串p自己找自己的匹配串。


完整代码


import java.io.*;
public class Main {
    static int N=100010;
    static int M=1000010;
    static char []p=new char[N];
    static int []ne=new int[N];
    static char []s=new char[M];
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int n=Integer.parseInt(br.readLine());
        String s1= br.readLine();
        for (int i = 1; i <=n; i++) {
            p[i]=s1.charAt(i-1);
        }
        int m=Integer.parseInt(br.readLine());
        String s2= br.readLine();
        for (int i =1; i <=m; i++) {
            s[i]=s2.charAt(i-1);
        }
        //构建前缀数组ne[]
        for(int i=2,j=0;i<=n;i++){
            while (j!=0 && p[i]!=p[j+1]) j=ne[j];
            if(p[i]==p[j+1]) j++;
            ne[i]=j;
        }
        //kmp匹配
        for(int i=1,j=0;i<=m;i++){
            while (j!=0 && s[i]!=p[j+1]) j=ne[j];
            // 匹配时将j++进行下一个字符得匹配
            if(s[i]==p[j+1]) j++;
            if(j==n){
                //当匹配成功时继续往下匹配
                j=ne[j];
                bw.write(i-n+" ");
            }
        }
        bw.flush();
        br.close();
        bw.close();
    }
}
目录
打赏
0
0
0
0
1
分享
相关文章
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
61 3
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
Java 面试资料中相关代码使用方法与组件封装方法解析
这是一份详尽的Java面试资料代码指南,涵盖使用方法与组件封装技巧。内容包括环境准备(JDK 8+、Maven/Gradle)、核心类示例(问题管理、学习进度跟踪)、Web应用部署(Spring Boot、前端框架)、单元测试及API封装。通过问题库管理、数据访问组件、学习进度服务和REST接口等模块化设计,帮助开发者高效组织与复用功能,同时支持扩展如用户认证、AI推荐等功能。适用于Java核心技术学习与面试备考,提升编程与设计能力。资源链接:[点此下载](https://pan.quark.cn/s/14fcf913bae6)。
67 6
Java 面试资料中相关代码使用方法与组件封装方法解析
这个AI把arXiv变成代码工厂,快速复现顶会算法!Paper2Code:AI论文自动转代码神器,多智能体框架颠覆科研复现
Paper2Code是由韩国科学技术院与DeepAuto.ai联合开发的多智能体框架,通过规划、分析和代码生成三阶段流程,将机器学习论文自动转化为可执行代码仓库,显著提升科研复现效率。
357 19
这个AI把arXiv变成代码工厂,快速复现顶会算法!Paper2Code:AI论文自动转代码神器,多智能体框架颠覆科研复现
基于Java 17 + Spring Boot 3.2 + Flink 1.18的智慧实验室管理系统核心代码
这是一套基于Java 17、Spring Boot 3.2和Flink 1.18开发的智慧实验室管理系统核心代码。系统涵盖多协议设备接入(支持OPC UA、MQTT等12种工业协议)、实时异常检测(Flink流处理引擎实现设备状态监控)、强化学习调度(Q-Learning算法优化资源分配)、三维可视化(JavaFX与WebGL渲染实验室空间)、微服务架构(Spring Cloud构建分布式体系)及数据湖建设(Spark构建实验室数据仓库)。实际应用中,该系统显著提升了设备调度效率(响应时间从46分钟降至9秒)、设备利用率(从41%提升至89%),并大幅减少实验准备时间和维护成本。
89 0
局域网行为监控软件 C# 多线程数据包捕获算法:基于 KMP 模式匹配的内容分析优化方案探索
本文探讨了一种结合KMP算法的多线程数据包捕获与分析方案,用于局域网行为监控。通过C#实现,该系统可高效检测敏感内容、管理URL访问、分析协议及审计日志。实验表明,相较于传统算法,KMP在处理大规模网络流量时效率显著提升。未来可在算法优化、多模式匹配及机器学习等领域进一步研究。
42 0
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
72 3
Java多线程基础
本文主要讲解多线程相关知识,分为两部分。第一部分涵盖多线程概念(并发与并行、进程与线程)、Java程序运行原理(JVM启动多线程特性)、实现多线程的两种方式(继承Thread类与实现Runnable接口)及其区别。第二部分涉及线程同步(同步锁的应用场景与代码示例)及线程间通信(wait()与notify()方法的使用)。通过多个Demo代码实例,深入浅出地解析多线程的核心知识点,帮助读者掌握其实现与应用技巧。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问