字符串模式匹配中BF算法和KMP算法的java实现

2024-05-29 23:18

本文主要是介绍字符串模式匹配中BF算法和KMP算法的java实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

关于BF算法和KMP算法的具体解释,文章【博客地址】:KMP字符串匹配算法与next数组中有推荐博客的具体地址,可以在这些博客中找到详细的解释。

以下只有具体的java代码实现:

BF算法

package com.algorithm;/*** 字符串模式匹配的 Brute-Force算法(暴力法)* @author Administrator**/public class StrMatchBF {public static void main(String[] args) {StrMatchBF strMatchBF = new StrMatchBF();String iniStr = "hello world";String patternStr = "world";System.out.println(strMatchBF.indexOfStr(iniStr, patternStr)); // 输出6}/*** 匹配字符串* @param iniStr    原始字符串* @param patternStr    模式字符串* @return  如果模式字符串在原始字符串中存在,返回模式字符串在原始字符串中第一次出现的索引。*/public int indexOfStr(String iniStr, String patternStr) {if(iniStr == null || iniStr.length() <= 0 || patternStr == null || patternStr.length() <=0)return -1;int iniLength = iniStr.length();int patternLength = patternStr.length();int i = 0, j = 0;while(i < iniLength && j < patternLength) {if(iniStr.charAt(i) == patternStr.charAt(j)) {i++;j++;} else {// 失配,回退i = i - j + 1;j = 0;}}if(j == patternLength)return i - patternLength;elsereturn -1;}
}

KMP算法

package com.algorithm;/*** 字符串匹配的KMP算法* @author Administrator**/public class StrMatchKMP {public static void main(String[] args) {StrMatchKMP strMatchKMP = new StrMatchKMP();String iniStr = "hello world";String patternStr = "world";System.out.println(strMatchKMP.indexOfStrKMP(iniStr, patternStr));}public int indexOfStrKMP(String iniStr, String patternStr) {if(iniStr == null || iniStr.length() <= 0 ||patternStr == null || patternStr.length() <= 0)return -1;// 得到模式串的next数组int[] nextArr = getNextArray(patternStr);int iniLength = iniStr.length();int patternLength = patternStr.length();int i = 0;  // 原始串索引int j = 0;  // 模式串索引while(i < iniLength && j < patternLength) {if(j == -1 || iniStr.charAt(i) == patternStr.charAt(j)) {i++;j++;} else {j = nextArr[j];}}if(j == patternLength)return i - patternLength;else return -1;}/*** 获取模式字符串的next数组* @param str* @return*/public int[] getNextArray(String str) {if(str == null || str.length() <= 0)return null;int length = str.length();int[] nextArr = new int[length];int j = 0;int k = -1;nextArr[0] = -1;while(j < length - 1) {if(k == -1 || str.charAt(j) == str.charAt(k)) {j++;    // 匹配,移动k++;if(str.charAt(j) != str.charAt(k))nextArr[j] = k;else nextArr[j] = nextArr[k];} else {k = nextArr[k];}}return nextArr;}
}

这篇关于字符串模式匹配中BF算法和KMP算法的java实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1014914

相关文章

SpringBoot集成EasyPoi实现Excel模板导出成PDF文件

《SpringBoot集成EasyPoi实现Excel模板导出成PDF文件》在日常工作中,我们经常需要将数据导出成Excel表格或PDF文件,本文将介绍如何在SpringBoot项目中集成EasyPo... 目录前言摘要简介源代码解析应用场景案例优缺点分析类代码方法介绍测试用例小结前言在日常工作中,我们经

基于Python实现简易视频剪辑工具

《基于Python实现简易视频剪辑工具》这篇文章主要为大家详细介绍了如何用Python打造一个功能完备的简易视频剪辑工具,包括视频文件导入与格式转换,基础剪辑操作,音频处理等功能,感兴趣的小伙伴可以了... 目录一、技术选型与环境搭建二、核心功能模块实现1. 视频基础操作2. 音频处理3. 特效与转场三、高

Python实现中文文本处理与分析程序的示例详解

《Python实现中文文本处理与分析程序的示例详解》在当今信息爆炸的时代,文本数据的处理与分析成为了数据科学领域的重要课题,本文将使用Python开发一款基于Python的中文文本处理与分析程序,希望... 目录一、程序概述二、主要功能解析2.1 文件操作2.2 基础分析2.3 高级分析2.4 可视化2.5

Java实现预览与打印功能详解

《Java实现预览与打印功能详解》在Java中,打印功能主要依赖java.awt.print包,该包提供了与打印相关的一些关键类,比如PrinterJob和PageFormat,它们构成... 目录Java 打印系统概述打印预览与设置使用 PageFormat 和 PrinterJob 类设置页面格式与纸张

使用Go实现文件复制的完整流程

《使用Go实现文件复制的完整流程》本案例将实现一个实用的文件操作工具:将一个文件的内容完整复制到另一个文件中,这是文件处理中的常见任务,比如配置文件备份、日志迁移、用户上传文件转存等,文中通过代码示例... 目录案例说明涉及China编程知识点示例代码代码解析示例运行练习扩展小结案例说明我们将通过标准库 os

Spring Security常见问题及解决方案

《SpringSecurity常见问题及解决方案》SpringSecurity是Spring生态的安全框架,提供认证、授权及攻击防护,支持JWT、OAuth2集成,适用于保护Spring应用,需配置... 目录Spring Security 简介Spring Security 核心概念1. ​Securit

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

SpringBoot改造MCP服务器的详细说明(StreamableHTTP 类型)

《SpringBoot改造MCP服务器的详细说明(StreamableHTTP类型)》本文介绍了SpringBoot如何实现MCPStreamableHTTP服务器,并且使用CherryStudio... 目录SpringBoot改造MCP服务器(StreamableHTTP)1 项目说明2 使用说明2.1