探究字符串匹配算法:暴力法与KMP算法的Java实现
探究字符串匹配算法:暴力法与KMP算法的Java实现
字符串匹配是计算机科学中的基本问题之一,它涉及在一个主串中查找特定的子串。在本文中,我们将深入探讨暴力法和KMP算法这两种常见的字符串匹配算法,并提供详细的Java代码示例。
1. 暴力法(Brute Force)
概念:暴力法是一种简单直观的字符串匹配算法。它在主串中逐个位置尝试匹配子串,如果匹配失败则将主串和子串的索引向后移动一位。
代码示例:
public class BruteForceMatcher {public static int bruteForceSearch(String text, String pattern) {int n = text.length();int m = pattern.length();for (int i = 0; i <= n - m; i++) {int j = 0;while (j < m && text.charAt(i + j) == pattern.charAt(j)) {j++;}if (j == m) {return i; // 匹配成功,返回索引}}return -1; // 未找到匹配}public static void main(String[] args) {String text = "ABABABAABCABAB";String pattern = "ABC";int index = bruteForceSearch(text, pattern);if (index != -1) {System.out.println("在索引 " + index + " 处找到匹配。");} else {System.out.println("未找到匹配。");}}
}
2. KMP算法
概念:KMP算法是一种高效的字符串匹配算法,它利用已经匹配过的信息来减少比较次数。它构建了一个部分匹配表(也称为最长前缀后缀表),用于在匹配过程中指导主串和子串的移动。
代码示例:
public class KMPMatcher {public static int[] computePrefixTable(String pattern) {int m = pattern.length();int[] prefixTable = new int[m];int j = 0;for (int i = 1; i < m; i++) {while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {j = prefixTable[j - 1];}if (pattern.charAt(i) == pattern.charAt(j)) {j++;}prefixTable[i] = j;}return prefixTable;}public static int kmpSearch(String text, String pattern) {int n = text.length();int m = pattern.length();int[] prefixTable = computePrefixTable(pattern);int j = 0;for (int i = 0; i < n; i++) {while (j > 0 && text.charAt(i) != pattern.charAt(j)) {j = prefixTable[j - 1];}if (text.charAt(i) == pattern.charAt(j)) {j++;}if (j == m) {return i - m + 1; // 匹配成功,返回索引}}return -1; // 未找到匹配}public static void main(String[] args) {String text = "ABABABAABCABAB";String pattern = "ABC";int index = kmpSearch(text, pattern);if (index != -1) {System.out.println("在索引 " + index + " 处找到匹配。");} else {System.out.println("未找到匹配。");}}
}
本文深入探讨了暴力法和KMP算法这两种常见的字符串匹配算法。通过详细的Java代码示例和解释,我们希望您能更好地理解这些算法的原理和应用。
相关文章:
探究字符串匹配算法:暴力法与KMP算法的Java实现
探究字符串匹配算法:暴力法与KMP算法的Java实现 字符串匹配是计算机科学中的基本问题之一,它涉及在一个主串中查找特定的子串。在本文中,我们将深入探讨暴力法和KMP算法这两种常见的字符串匹配算法,并提供详细的Java代码示例。 …...
前端面试:【浏览器与渲染引擎】工作原理与渲染流程
嗨,亲爱的读者!你是否曾经好奇过当你在浏览器中输入URL并按下回车时,网页是如何显示在你的屏幕上的?这背后涉及了复杂的浏览器工作原理和渲染流程。本文将带你深入了解浏览器如何工作以及网页如何被渲染出来。 1. 浏览器的工作原理…...

PySide6学习笔记--gui小模版使用
一、界面绘制 1.desiner画图 2.画图代码 # -*- coding: utf-8 -*-################################################################################ ## Form generated from reading UI file t1gui.ui ## ## Created by: Qt User Interface Compiler version 6.5.2 ## ##…...
如何用Python实现冒泡排序
1 问题 冒泡排序是一种简单的排序算法,它也是一种稳定排序算法。其实现原理是重复扫描待排序序列,并比较每一对相邻的元素,当该对元素顺序不正确时进行交换。一直重复这个过程,直到没有任何两个相邻的元素可以交换,就表…...

C++Qt堆叠窗体的使用案例
本博文源于笔者最近学习的Qt,内容讲解堆叠窗体QStackedWidget案例,效果是选择左侧列表框中不同的选项时,右侧显示所选的不同的窗体。 案例效果 案例书写过程 控件都是动态创建的,因此.h文件需要创建控件,.cpp书写业务…...

Linux之套接字UDP实现网络通信
Linux之套接字UDP实现网络通信 文章目录 Linux之套接字UDP实现网络通信1.引言2.具体实现2.1需要知道的套接字接口1.socket()2.bind()3.recvfrom()4.sendto() 2.2服务器端server.hpp2.3服务器端server.cc2.4客户端Client.cc 1.引言 套接字(Socket)是计算机网络中实现网络通信…...

Matlab绘制二值图像
二值化介绍 只有黑白两种颜色的图像称为黑白图像或单色图像,是指图像的每个像素只能是黑或者白,没有中间的过渡,故又称为二值图像。其特点是二值图像的像素值只能为0和1,分别代表黑色和白色,图像中的每个像素值用1位存…...

Kali 网络参数的配置
手工方式 Wired 有线 Woreless 无线 图形化的网络管理器(依赖的服务:NetworkManager) ┌──(root㉿kali)-[~] └─# systemctl status NetworkManager ● NetworkManager.service - Network ManagerLoaded: loaded (/lib/systemd/system/N…...

在 Redis 中处理键值 | Navicat
Redis 是一个键值存储系统,允许我们将值与键相关联起来。与关系型数据库不同的是, 在Redis 中,不需要使用数据操作语言 (DML) 和查询语法,那么我们如何进行数据的写入、读取、更新和删除操作呢?…...

RedisTemplate和StringRedisTemplate的区别、对比
学习 Jedis、RedisTemplate、StringRedisTemplate之间的比较 博客中提到:一. Jedis是Redis官方推荐的面向Java的操作Redis的客户端。 二. RedisTemplate,StringRedisTemplate是SpringDataRedis中对JedisApi的高度封装。SpringDataRedis相对于Jedis来说可以方便地更…...

使用ChatGPT进行创意写作的缺点
Open AI警告ChatGPT的使用者要明白此工具的局限性,更不应完全依赖。作为一位创作者,这一点非常重要,应尽可能地避免让版权问题或不必要的文体问题出现在自己的作品中。[1] 毕竟使用ChatGPT进行创意写作目前还有以下种种局限或缺点[2]…...

七、任务优先级和Tick
1、任务与中断的优先级 (1)相同优先级任务轮流执行。 (2)高优先级任务打断低优先级任务。 (3)中断可以打断所有优先级的任务。 2、任务优先级 (1)优先级的取值范围是:0~(configMAX_PRIORITIES – 1),数值越大优先级越高。 (2)FreeRTOS会确保最高优…...
Python——三目运算语句
本文基于python3。 目录 1、三目运算语句的定义2、三目运算语句:包含逻辑运算符 (and、or、not)1、 包含 and2、包含 or3、包含 not4、包含 and、or、not 3、三目运算语句:使用多个if ... else ...形式4、三目运算语句:在列表(li…...

C 实现Window/DOS 键盘监听事件
今天是重新复习C语言实现的第一天,今天想编写C 对Windwos/Dos 键盘事件的学习。但是我在安装Visual Studio 2022 没有安装MFC 框架,今天记录下VS追加 MFC框架。 Visual Studio 2022 追加MFC 1、打开vs,点击创建新项目,右侧滑动框…...
在vue中使用 axios 访问 API
Vue 不像 jQuery 内置了 ajax 请求函数,在 Vue 中没有提供这样的功能。所以当我们需要在 Vue 中和服务端进行通信的时候可选择的方式会更灵活一些。 所以 Vue 给了我们更多的选择空间,例如我们可以使用下面的可选方案: 原生的 XMLHttpReques…...

java八股文面试[java基础]——浅拷贝和深拷贝
自验证:创建Class Student两个类, Student中含有Class对象 public class Class implements Cloneable {public String getName() {return name;}public void setName(String name) {this.name name;}private String name;public Class(String name) {t…...

【DC-DC的原理图及Layout设计要点】
文章目录 前言1.DC-DC的环流2.PCB布局要点3.输入电容器的布局4.续流二极管的布局5.热焊盘 前言 在开关电源的设计中,PCB布局设计与电路设计同样重要。合理的布局可以避免电源电路引起的各种问题。不合理的布局可能导致输出和开关信号叠加引起噪声增加、调节性能恶化…...

TCP可靠性机制
确认号/序列号/ACK TCP帮助确保数据的准确传递。为了做到这一点,其使用了一些特殊的标记和信息,其中包括序号、确认号和ACK字段。 其中,它将每个字节的数据都进行了编号. 即为序列号. 序列号:就像给书中的每一页都编了号码一样&a…...

solidity0.8.0的应用案例13:数字签名及应用:NFT白名单
以太坊中的数字签名ECDSA,以及如何利用它发放NFT白名单 代码中的ECDSA库由OpenZeppelin的同名库简化而成。 数字签名 如果你用过opensea交易NFT,对签名就不会陌生。下图是小狐狸(metamask)钱包进行签名时弹出的窗口,它可以证明你拥有私钥的同时不需要对外公布私钥。 …...

视频集中存储/直播点播平台EasyDSS内核无法启动是什么原因?
视频推拉流EasyDSS视频直播点播平台,集视频直播、点播、转码、管理、录像、检索、时移回看等功能于一体,可提供音视频采集、视频推拉流、播放H.265编码视频、存储、分发等视频能力服务。 有用户反馈,下载了视频直播点播平台EasyDSS最新版本&a…...

利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...

linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...