探究字符串匹配算法:暴力法与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…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
