Java怎么实现KMP算法
发表于:2025-01-20 作者:千家信息网编辑
千家信息网最后更新 2025年01月20日,本篇内容主要讲解"Java怎么实现KMP算法",感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习"Java怎么实现KMP算法"吧!KMP 算法KMP (Knuth
千家信息网最后更新 2025年01月20日Java怎么实现KMP算法
本篇内容主要讲解"Java怎么实现KMP算法",感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习"Java怎么实现KMP算法"吧!
KMP 算法
KMP (Knuth-Morris-Pratt), 是一种改进的字符串匹配算法. KMP 算法解决了暴力匹配需要高频回退的问题, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 从而大大提高效率. 如图:
举个例子 (字符串 "abcabcdef" 匹配字符串 "abcdef"):
次数 | 暴力匹配 | KMP 算法 | 说明 |
---|---|---|---|
1 | a bcabcdef a bcdef | a bcabcdef a bcdef | a 和 a 匹配 |
2 | ab cabcdef ab cdef | ab cabcdef ab cdef | ab 和 ab 匹配 |
3 | abc abcdef abc def | abc abcdef abc def | abc 和 abc 匹配 |
4 | abca bcdef abcd ef | abca bcdef abcd ef | abca 和 abcd 不匹配, 回退. 暴力匹配回退到索引 1, 即 "b", KMP 算法索引跳置 3, 即 "a" |
5 | ab cabcdef a bcdef | abca bcdef a bcdef | 暴力匹配 b 和 a 不匹配, 后移. KMP 算法 a 和 a 匹配 |
6 | abc abcdef a bcdef | abcab cdef ab cdef | 暴力匹配 c 和 a 不匹配, 后移. KMP 算法 ab 和 ab 匹配 |
7 | abca bcdef a bcdef | abcabc def abc def | 暴力匹配 a 和 a 匹配. KMP 算法 abc 和 abc 匹配 |
8 | abcab cdef ab cdef | abcabcd ef abcd ef | 暴力匹配 ab 和 ab 匹配. KMP 算法 abcd 和 abcd 匹配 |
9 | abcabc def abc def | abcabcde f abcde f | 暴力匹配 abc 和 abc 匹配. KMP 算法 abcde 和 abcde 匹配 |
10 | abcabcd ef abcd ef | abcabcdef abcdef | 暴力匹配 abcd 和 abcd 匹配. KMP 算法 abcdef 和 abcdef 匹配 , 匹配完成 |
11 | abcabcde f abcde f | abcabcdef abcdef | 暴力匹配 abcde 和 abcde 匹配. KMP 算法匹配完成 |
12 | abcabcdef abcdef | abcabcdef abcdef | 暴力匹配 abcd 和 abcd 匹配, 匹配完成. KMP 算法匹配完成 |
部分匹配表
部分匹配表 (Partial Match Table) 指的是 "前缀" 和 "后缀" 的最长共有元素的长度.
举个例子, 字符串 "ABCDABD" 的前缀与后缀:
字符串 | 前缀 | 后缀 | 共同部分 | 值 |
---|---|---|---|---|
A | NaN | NaN | NaN | 0 |
AB | A | B | NaN | 0 |
ABC | A, AB | C, BC | NaN | 0 |
ABCD | A, AB, ABC | D, CD, BCD | NaN | 0 |
ABCDA | A, AB, ABC, ABCD | A, DA, CDA, BCDA | A | 1 |
ABCDAB | A, AB, ABC, ABCD, ABCDA | B, AB, DAB, CDAB, BCDAB | AB | 2 |
ABCDAB | A, AB, ABC, ABCD, ABCDA, ABCDAB | D, BD, ABD, DABD, CDABD, BCDABD | NaN | 0 |
KMP 算法实现
重点:
KMP 算法中移动的位数 = 已匹配的字符数 - 对应的部分匹配值
import java.util.Arrays;public class KMPMatch { public static int Match(String str1, String str2, int[] next) { // 初始化索引 int i = 0; int j = 0; for (; i < str1.length(); i++) { if (j > 0 && str1.charAt(i) != str2.charAt(j)) { // 不匹配, 回退 i = i - next[j - 1]; j = 0; } // 匹配 if (str1.charAt(i) == str2.charAt(j)) { j++; } // 返回索引 if (j == str2.length()) { return i - j + 1; } } return -1; } // 部分匹配 public static int[] getNext(String s) { // 定义数组 int next[] = new int[s.length()]; // 初始化i, j int i = 0; int j = -1; next[0] = -1; // 遍历 while (i < s.length() - 1) { if (j == -1 || s.charAt(i) == s.charAt(j)) { // 匹配成功 next[i] = j + 1; i++; j++; } else { //一旦不匹配成功j回退到-1 j = -1; } } return next; } public static void main(String[] args) { // 字符串1 String str1 = "BBCABCDAB ABCDABD"; // 字符串2 String str2 = "ABCDABD"; // 匹配表 int[] next = getNext(str2); System.out.println(Arrays.toString(next)); // KMP算法 int result = Match(str1, str2, next); System.out.println(result); }}
输出结果:
[0, 0, 0, 0, 1, 2, 0]
10
到此,相信大家对"Java怎么实现KMP算法"有了更深的了解,不妨来实际操作一番吧!这里是网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
算法
暴力
字符
字符串
部分
索引
前缀
后缀
成功
例子
内容
后移
学习
实用
更深
最长
位数
位置
元素
兴趣
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
数据库原理及应用的作用
游戏组队吃服务器吗
实时公交软件开发说明
网络安全法国家标准的要求
数据库持续集成
地理空间数据库的元数据
课程评价系统软件开发
视频终端服务器
研究生论文数据库哪个好
公安局网络安全信息中心
博客类数据库设计
网络安全测量
显示数据库的语法格式是
重庆系统软件开发机构
计算机网络技术网测视频
杭州互联网软件开发定制费用
不合格品数据库建立的意义
北海计算机网络技术学校
5g网络技术对未来的影响
部门网络安全工作
中学生网络安全教育讲座
服务器php版本升级
网络安全宣传周 总体方案
根域名服务器怎么组件
网络安全模式下玩dnf
数据库保险箱
外卖预订系统数据库
yii框架数据库配置
idc服务器违法吗
数据库技术发展的各阶段