字符串匹配算法大全JAVA版（BF、RK、BM以及KMP代码理解）

48 阅读 0 评论 32 点赞

我是靠谱客的博主干净小白菜，最近开发中收集的这篇文章主要介绍字符串匹配算法大全JAVA版（BF、RK、BM以及KMP代码理解），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

如果对这几个算法的原理尚有疑问，推荐文章

字符串匹配算法原理，再回来理解个中代码更清晰

BF算法（暴力算法）

private static int bfSearch(String desString, String subString) {
if (desString == null || subString == null) {
return -1;
}
// 1、主串长度
int m = desString.length();
// 2、模式串长度
int n = subString.length();
if (n > m) {
throw new RuntimeException("主串长度不能小于模式串的长度");
}
// 3、定义索引变量: i-目标串的索引，j-模式串的索引
int i = 0, j = 0;
// 结束条件：如果目标串剩余字符的数量小于模式串的长度时，证明无匹配成功数据
while (i < m - n + 1) {
for (; j < n && i < m; i++, j++) {
if (desString.charAt(i) != subString.charAt(j)) {
i = i - j + 1;
j = 0;
break;
}
}
if (j == n) {
return i - j;
}
}
return -1;
}

RK算法


private static int rabinKarpSearch(String desString, String subString) {
if (desString == null || subString == null) {
return -1;
}
// 1、主串长度
int m = desString.length();
// 2、模式串长度
int n = subString.length();
if (n > m) {
throw new RuntimeException("主串长度不能小于模式串的长度");
}
// 3、获取模式串的hash值
int patternCode = hash(subString);
// 4、计算主串中与模式串长度相同第一个子串的hash值
int strCode = hash(desString.substring(0, n));
// 5、逐位比较hash值
for (int i = 0; i < m - n + 1; i++) {
// 如果hash值相等，为了防止hash碰撞产生的误差，故还需对字符串进行比较，以保证确实相等
if (patternCode == strCode && compareString(i, desString, subString)) {
return i;
}
// 判断是否为最后一轮，如果是最后一轮，则不再进行hash计算
if (i < m - n) {
strCode = nextHash(desString, strCode, i, n);
}
}
return -1;
}
/**
* 下一位的hash值计算
*
* @param desString 目标串
* @param strCode
当前的hash值
* @param index
当前hash值的所计算的字符串在目标串起始位置
* @param offset
hash值计算的串长度
* @return int
* @Author muyi
* @Date 14:03 2020/12/7
*/
private static int nextHash(String desString, int strCode, int index, int offset) {
/**
* 比如 计算 ABCD 中 CD 的hash值，
* 已知 BC的hash值为3，index = 1,offset = 2
* 所以 CD的hash值等于 BC - B + D
*/
// 1、减去起始位置字符的hash值
strCode -= desString.charAt(index) - 'A';
// 2、加上新增为字符的hash值
strCode += desString.charAt(index + offset) - 'A';
return strCode;
}
private static boolean compareString(int index, String desString, String subString) {
String temp = desString.substring(index, index + subString.length());
return temp.equals(subString);
}
/**
* @param subString 字符串
* @return int 约定计算模式的hash值
* @Author muyi
* @Date 14:00 2020/12/7
*/
private static int hash(String subString) {
int hashCode = 0;
int length = subString.length();
int i = 0;
/**
* 这里采用最简单的hashcode计算方式：
* 把A当做0，把B当中1，把C当中2.....然后按位相加
*/
while (i < length) {
hashCode += subString.charAt(i) - 'A';
i++;
}
return hashCode;
}

BM算法（阉割版有缺陷，只为后续代码理解提供支撑）

private static int boyerMooreSearch(String desString, String subString) {
if (desString == null || subString == null) {
return -1;
}
// 1、主串长度
int m = desString.length();
// 2、模式串长度
int n = subString.length();
if (n > m) {
throw new RuntimeException("主串长度不能小于模式串的长度");
}
// 主串的起始位置
int start = 0;
while (start <= m - n) {
int index;
// 根据模式串，从后往前查找坏字符
for (index = n - 1; index >= 0; index--) {
if (desString.charAt(index + start) != subString.charAt(index)) {
// 找到第一个坏字符，
break;
}
}
// index < 0 说明遍历整个模式串，没有找到坏字符，说明已经找到匹配的字符串
if (index < 0) {
return start;
}
// 从模式串index位置逆序找到第一个坏字符所在的索引值
int reverserOrderBadCharIndex = findBadCharIndex(subString, desString.charAt(start + index), index);
/**
* 计算坏字符产生的位移
*
如果 reverserOrderBadCharIndex >= 0：
*
说明在模式串中找到了坏字符的索引值（即模式串中存在坏字符），故偏移量为 index（当前出现坏字符时，模式串对应的索引值）与坏字符索引之间的差值
*
eg:
*
模式串 = E X A M P L E，当扫描到 index = 5,即L时，主串出现坏字符A，而坏字符A在模式串中最后一次出现的索引是 2，
*
故偏移位置 = 5 -2 = 3
*
如果 reverserOrderBadCharIndex < 0:
*
说明在模式串中未找到索引值，故整个偏移量为 index+1（实际就是模式串的长度值），即模式串整体移动到index下一位，再进行比较
*/
int badCharOffset = reverserOrderBadCharIndex >= 0 ? index - reverserOrderBadCharIndex : index + 1;
// 主串起始位置进行偏移操作
start += badCharOffset;
}
return -1;
}
/**
* 获取index之前，第一个与坏字符相等的索引值
*
* @param subString 待查找的字符串
* @param badChar
坏字符
* @param index
起始索引
* @return int 坏字符索引值
* @Author muyi
* @Date 14:45 2020/12/7
*/
private static int findBadCharIndex(String subString, char badChar, int index) {
// index之前，本身不算，故计算的起始位置为index-1
for (index = index - 1; index >= 0; index--) {
if (subString.charAt(index) == badChar) {
return index;
}
}
return -1;
}

上面的算法每次碰到坏字符的时候都会去查找一次坏字符的位置，无端增加了时间复杂度，故我们可以先计算坏字符的索引位置，最后再匹配模式串，代码如下：

BM算法（阉割改良版，只为后续代码理解提供支撑）


/**
* 以模式串的字符数组为例，假定模式串中每一个字符都是坏字符，寻找他们在模式串中最后一次出现的索引值
*
* @param subString 模式串
* @return int[]
索引数组
* @Author muyi
* @Date 10:40 2020/12/8
*/
private static int[] buildBadCharacterIndexes(String subString) {
// 1、获取字符串的长度
int sLen = subString.length();
// 2、英文字符的种类，2^8，故初始化 badCharacterOffsets 的长度为256，该数组的含义为 下标为字符的ascii码值，值为偏移值
final int CHARACTER_SIZE = 256;
int[] badCharacterOffsets = new int[CHARACTER_SIZE];
// 3、默认 -1，表示未出现在模式串中
Arrays.fill(badCharacterOffsets, -1);
// 4、如果模式串中的出现了该字符，那么记录该字符在模式串中最后一次出现的位置
for (int i = 0; i < sLen; i++) {
int ascii = subString.charAt(i);
badCharacterOffsets[ascii] = i;
}
return badCharacterOffsets;
}

获取坏字符的代码改成如下，即可：

// 循坏外增加先获取模式坏字符索引数组
int[] ints = buildBadCharacterIndexes(subString);
/**
* 获取坏字符索引值
*
注意：这里的坏字符是以主串为准，所以在取索引的时候，需要对主串坏字符的索引位置进行计算
*
即：坏字符在主串的索引值 = 主串开始索引值 + 对比工程中，出现坏字符时模式串的索引值
*/
int badCharIndex = desString.charAt(index + start);
int reverserOrderBadCharIndex = ints[badCharIndex];

BM算法（好后缀与坏字符完整版版）

private static int boyerMooreSearch1(String desString, String subString) {
int subStrLength = Optional.ofNullable(subString).map(item -> item.getBytes().length).orElse(0);
int mainStrLength = Optional.ofNullable(desString).map(item -> item.getBytes().length).orElse(0);
if (subStrLength == 0 || mainStrLength == 0) {
return -1;
}
// 1、填装好后缀数组
int[] suffix = new int[subStrLength];
boolean[] prefix = new boolean[subStrLength];
fillFix(subString, suffix, prefix);
// 2、获取子串坏字符索引值表
int[] buildBadCharacterIndexes = buildBadCharacterIndexes(subString);
// 主串字符查询开始索引值
int desStartIndex = 0;
int desStrLen = desString.length();
int subStrLen = subString.length();
// 3、循环对主、模式串的字符进行对比判断，跳出条件是：如果主串未判断字符已经小于模式串的长度
while (desStartIndex <= desStrLen - subStrLen) {
// 模式串索引值，从后往前进行匹配
int subStrIndex = subStrLen - 1;
for (; subStrIndex >= 0; subStrIndex--) {
char desCharAt = desString.charAt(desStartIndex + subStrIndex);
char subCharAt = subString.charAt(subStrIndex);
if (desCharAt != subCharAt) {
break;
}
}
// 如果模式串字符已经全部进行了匹配，则说明已找到匹配字符串，返回主串的起始值即可
if (subStrIndex < 0) {
return desStartIndex;
}
// 坏字符偏移值
int badCharMoveLen = buildBadCharacterIndexes[subString.charAt(subStrIndex)];
// 好后缀偏移值
int suffixCharMoveLen = getSuffixCharIndex(subStrIndex, subStrLength, suffix, prefix);
// 避免偏移量为负数，故偏移量为取二者的最大值
desStartIndex += Math.max(badCharMoveLen, suffixCharMoveLen);
}
return -1;
}
/**
* @param badCharIndex 坏字符索引值
* @param subStrLength 模式串长度
* @param suffix
好后缀数组表
* @param prefix
* @return int 好后缀偏移值
* @Author muyi
* @Date 15:53 2020/12/9
*/
private static int getSuffixCharIndex(int badCharIndex, int subStrLength, int[] suffix, boolean[] prefix) {
// 好后缀的长度
int goodSuffixLen = subStrLength - badCharIndex - 1;
// 根据长度，获取好后缀的偏移值
int suffixCharMoveLen = suffix[goodSuffixLen];
// case1：如果偏移值不等于-1；说明已经在模式串中找到另一个与好后缀子串，直接返回偏移值即可
if (suffixCharMoveLen != -1) {
return badCharIndex - suffixCharMoveLen + 1;
}
/**
* case2：避免在模式串的最右端出现好后缀的子串，造成偏移量过大
*
eg: ABCDMNEF A B C, 假如EFABC作为好后缀，在模式串中获取与好后缀相等的子串，不存在，这时滑动结果为：
*
A B C DMNEFABC，造成滑动过多，实际上在好后缀的子串中是存在匹配的
*
A B C DMNEFABC，正确的滑动情况
* r：好后缀子串的遍历的起始值，即好后缀包含该索引的值。
* badCharIndex + 2：以badCharIndex作为分界点的好后缀不存在
*
当 badCharIndex+1 时，当前索引值与以 badCharIndex 为分界点的好后缀存在重复，故此处+2
*
eg: A B C F H A B C ,假如现在 F的索引值为 badCharIndex = 3，此时的好后缀 = H A B C
*
badCharIndex+1 = 4,此时的好后缀 = H A B C，
*
badCharIndex+2 = 5,此时的好后缀 = A B C，
*/
for (int r = badCharIndex + 2; r < subStrLength; ++r) {
/**
* 好后缀的长度 = 模式串的长度 - 好后缀的起始索引
* eg；A B C F H A B C 其中 A B C 作为前缀子串，其起始索引 = 5，
*
A B C F H A B C ，偏移5个位置后，
*/
if (prefix[subStrLength - r] == true)
return r;
}
// case3：在子串中即没有与好后缀匹配的子串，也没有与好后缀子串匹配的前缀子串，则模式串的长度即为偏移量
return subStrLength;
}
/**
* 两个数组的下标都是 好后缀的长度，而值则是 与好后缀相等的 模式串子串 的最大起始索引值，要抛开本身
*
* @param subString 模式串
* @param suffix
模式串好后缀在前缀中最大的起始位置数组
* @param prefix
用于存放当前好后缀是否为模式串的前缀子串
* @return void
* @Author muyi
* @Date 13:29 2020/12/8
*/
private static void fillFix(String subString, int[] suffix, boolean[] prefix) {
int length = subString.length();
// index 为好后缀数组、模式串与前缀子串是否相等数组的索引值
for (int index = length - 1; index >= 0; index--) {
suffix[index] = -1;
prefix[index] = false;
}
int subStrLength = subString.length();
for (int index = subStrLength - 1; index > 0; index--) {
String patternString = subString.substring(index);
for (int j = index - 1; j >= 0; j--) {
String tempString = subString.substring(j, j + patternString.length());
if (tempString.equals(patternString)) {
suffix[patternString.length() - 1] = j;
if (j == 0) {
prefix[patternString.length() - 1] = true;
}
break;
}
}
}
}

KMP算法
这里获取组装next数组的方式多种多样，这里只列举了其中一种，理解KMP算法的实现原理最重要。

private static int kmpSearch1(String desString, String subString) {
if (desString == null || desString.length() == 0 || subString == null || subString.length() == 0) {
return -1;
}
// 1、计算next数组
int[] next = getNext1(subString);
// 2、定义一个指针用于指向主串的第一个字符位置
int x = 0;
// 3、定义一个指针用于指向目标串的第一个字符位置
int y = 0;
// 4、定义一个循环，用于实现字符串的匹配操作
while (x < desString.length() && y < subString.length()) {
char mainTemp = desString.charAt(x);
char subTemp = subString.charAt(y);
// 如果两个字符相等，主串和模式串的索引都向后移动一位
if (mainTemp == subTemp) {
x++;
y++;
continue;
}
// 如果不相等
if (mainTemp != subTemp) {
// 判断模式串是否是已经指向串首，
if (y > 0) {
// 如果没有指向串首，则根据当前索引获取最大前后缀公共子串的长度，继续比较
y = next[y];
} else {
// 如果已经指向串首，那么主串指针索引移动一位，继续比较
x++;
}
}
}
if (y == subString.length()) {
return x - y;
}
return -1;
}
private static int[] getNext1(String subString) {
int[] next = new int[subString.length()];
/**
* 从索引2开始查询，j表示相等前后缀子串的长度，初始值为0
* 当索引等于0，没有前后缀，故最大公共前后缀长度为0
* 当索引等于1，只有前缀没有后缀，最大公共前后缀长度同样为0
* i 表示模式串的索引值
* j 模式串上一索引值所匹配的最大公共前后子串长度值，默认值是0，或者 j = next[1]
*/
for (int i = 2, j = 0; i < subString.length(); i++) {
while (j > 0 && subString.charAt(i - 1) != subString.charAt(j)) {
j = next[j - 1];
}
// 如果相等，相等前后缀子串的长度+1
if (subString.charAt(i - 1) == subString.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}