KMP算法-字符串匹配问题
2022/6/6 1:20:18
本文主要是介绍KMP算法-字符串匹配问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.背景
2.代码
package com.ldp.algorithm.demo02KMP; import org.junit.Test; import java.util.Arrays; /** * @create 05/29 9:39 * @description */ public class Test01Search { @Test public void test01() { String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD"; int violenceSearch = violenceSearch(str1, str2); System.out.println("violenceSearch:" + violenceSearch); int kmpSearch = kmpSearch(str1, str2); System.out.println("kmpSearch:" + kmpSearch); } /** * 暴力匹配算法 * 字符串匹配 * * @param str1 源字符串 * @param str2 需要查找的字符串,即查找的关键字符串 * @return 返回-1表示没有找到,否则返回找到的下标 */ public int violenceSearch(String str1, String str2) { char[] chars1 = str1.toCharArray(); char[] chars2 = str2.toCharArray(); int length1 = chars1.length; int length2 = chars2.length; int i = 0;// chars1的下标 int j = 0;// chars2的下标 while (i < length1 && j < length2) { if (chars1[i] == chars2[j]) { i++; j++; } else { // i向前移动1位,j=0,重新开始匹配 i = i + 1 - j; j = 0; } } // 匹配到的情况,返回匹配到i的下标 // 为什么这里没有j-1=length2,因为在匹配完成后j++了 if (j == length2) { return i - j; } return -1; } /** * 暴力匹配算法 * 字符串匹配 * * @param str1 源字符串 * @param str2 需要查找的字符串,即查找的关键字符串 * @return 返回-1表示没有找到,否则返回找到的下标 */ public int kmpSearch(String str1, String str2) { // 生成部分匹配表 int[] kmpSurfaceArray = createKmpSurface(str2); System.out.println(Arrays.toString(kmpSurfaceArray)); // 遍历(字符串str1的下标始终向前移动) for (int i = 0, j = 0; i < str1.length(); i++) { // kmp算法核心点 while (j > 0 && str1.charAt(i) != str2.charAt(j)) { // 这一步在配置表中很可能值为零 kmpSurfaceArray = [0, 0, 0, 0, 1, 2, 0] j = kmpSurfaceArray[j - 1]; } if (str1.charAt(i) == str2.charAt(j)) { j++; } if (j == str2.length()) { // 已完成匹配 return i - j + 1; } } return -1; } /** * 生成kmp部分匹配表 * * @param dest * @return */ public int[] createKmpSurface(String dest) { int[] array = new int[dest.length()]; // 如果字符串长度是1,部分匹配值就是0 array[0] = 0; for (int i = 1, j = 0; i < dest.length(); i++) { // kmp算法的核心点 while (j > 0 && dest.charAt(i) != dest.charAt(j)) { j = array[j - 1]; } if (dest.charAt(i) == dest.charAt(j)) { j++; } array[i] = j; } return array; } }
完美!
这篇关于KMP算法-字符串匹配问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?