探究字符串匹配算法:暴力法与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…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...

NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
如何配置一个sql server使得其它用户可以通过excel odbc获取数据
要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据,你需要完成以下配置步骤: ✅ 一、在 SQL Server 端配置(服务器设置) 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到:SQL Server 网络配…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...