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

本文主要是介绍字符串模式匹配中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;}
}