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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
* 以模式串的字符数组为例，假定模式串中每一个字符都是坏字符，寻找他们在模式串中最后一次出现的索引值
*
* @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;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
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;
}
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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;
}