KMP算法
2021/5/19 12:25:25
本文主要是介绍KMP算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
KMP算法
1.KMP算法的应用场景:字符串匹配问题。
假设str1 = BBC ABCBAB ABCDABCDABDE, str2 = ABCDABD,然后判断str1是否还有str2,如果存在,就返回第一次出现的位置 ,如果没有返回-1。
解法1:暴力匹配算法
假设str1匹配到i位置,字串str2匹配到j位置,则
1)如果当前匹配成功(即str[i] = str[j]),则i++, j++,继续匹配下一个字符。
2)如果匹配不成功(即str[i]!=str[j]),令i = i-j+1(i回到开始匹配的字符的后一个位置), j = 0(回到初始位置),相当于每次匹配失败,i回溯,j重置。
由此可以看出暴力匹配方法会有大量回溯,浪费大量时间,不可行。
2.KMP算法介绍
1)KMP算法是一个解决模式串在文本串是否出现过,如果出现过,返回最早出现的位置的经典算法。
2)部分匹配表产生
字符串:“bread”; 前缀: b, br, bre, bred 后缀:read, ead, ad, d
部分匹配值就是前缀和后缀的最长的共有元素的长度,以“ABCDABD”为例:
“A”的前缀和后缀都为空集,所以共有元素的长度为0。
“AB”的前缀为[A],后缀为[B],共有长度为0。
“ABC”的前缀[A,AB], 后缀为[BC,C],共有长度为0。
"ABCD"的前缀[A,AB,ABC],后缀为[BCD,CD,D],共有长度为0。
“ABCDA”的前缀[A,AB,ABC,ADCD],后缀为[BCDA,CDA,DA,A],共有元素为“A”,所以共有长度为1;
“ABCDAB”的前缀[A,AB,ABC,ABCD,ABCDA],后缀[BCDAB,CDAB,DAB,AB,B],共有元素为“AB”,所以共有长度为2;
“ABCDABD”的前缀[A,AB,ABC,ABCD,ABCDA,ABCDAB],后缀[BCDABD,CDABD,DABD,ABD,BD,D],共有长度为0;
由上可得出部分匹配表为
搜索词 | A | B | C | D | A | B | D |
---|---|---|---|---|---|---|---|
部分匹配值 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
解法2 :
package com.ll.kmp; public class KMPAlgorithm { public static void main(String[] args) { String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD"; int[] next = kmpNext(str2); System.out.print(kmpSearch(str1, str2, next)); } /** * kmp匹配算法 * * @param str1 源字符串 * @param str2 目标字符串 * @param next 部分匹配表 * @return 返回对应位置,未找到返回-1 */ public static int kmpSearch(String str1, String str2, int[] next) { for (int i = 0, j = 0; i < str1.length(); i++) { // 需要处理str1.charAt(i) != str2.charAt(j),去调整j的大小 while (j > 0 && str1.charAt(i) != str2.charAt(j)) { j = next[j - 1]; } // 字符匹配成功 if (str1.charAt(i) == str2.charAt(j)) { j++; } if (j == str2.length()) { return i - j + 1; } } return -1; } /** * 获取字符串的部分匹配表 * * @param dest 目标字符串 * @return */ public static int[] kmpNext(String dest) { // 创建部分匹配表 int[] next = new int[dest.length()]; next[0] = 0; // 如果字符串长度位1, 部分匹配值为0; for (int i = 1, j = 0; i < dest.length(); i++) { while (j > 0 && dest.charAt(i) != dest.charAt(j)) { j = next[j - 1]; } // 如dest.charAt(i) == dest.charAt(j),则部分匹配值j++ if (dest.charAt(i) == dest.charAt(j)) { j++; } next[i] = j; } return next; } }
这篇关于KMP算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)