BF算法
BF（Brute Force），暴力检索法是最好想到的算法，也最好实现。首先将原字符串和子串左端对齐，逐一比较；如果第一个字符不能匹配，则子串向后移动一位继续比较；如果第一个字符匹配，则继续比较后续字符，直至全部匹配。 时间复杂度：O(nm)。其中 n 为原字符串长度，m 为子串长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| function BF(haystack, needle) {
let j=0;
for(let i = 0; i < haystack.length; i++){
if(haystack[i] == needle[j]){
if(j == 0){
re = i;
}
j = j+1;
if(j == needle.length) {
return i-j+1;
}
}else {
if(j !== 0){
i=i-j;
}
j=0;
}
}
return -1;
}
|
RK算法
RK算法在BF基础上，引入哈希算法。通过字符串的哈希值的比较替换掉字符串之间的比较，从而降低算法的时间复杂度。RK算法整体的时间复杂度为O(n)。其中 n 为原字符串长度。
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
|
function hash(string) {
let hash = 0;
for (let i = 0; i < string.length; i++) {
hash += 26 * hash + string[i].charCodeAt();
}
return hash;
}
function isMatch (str, dest) {
if (str.length !== dest.length) {
return false;
}
for (var i = 0; i < str.length; i++) {
if (str[i] !== dest[i]) {
return false;
}
}
return true;
}
function RK(haystack, needle) {
let needleHash = hash(needle);
for(let i=0; i<=(haystack.length - needle.length); i++){
let subStr = haystack.substr(i, needle.length);
if (hash(subStr) === needleHash && isMatch(subStr, needle)) {
return i;
}
}
return -1;
}
|
BM算法
BM算法的核心思想是通过将模式串沿着主串大踏步的向后滑动，从而大大减少比较次数，降低时间复杂度。而算法的关键在于如何兼顾步子迈得足够大与无遗漏，同时要尽量提高执行效率。这就需要模式串在向后滑动时，遵守坏字符规则与好后缀规则，同时采用一些技巧。
坏字符
坏字符规则：从后往前逐位比较模式串与主串的字符，当找到不匹配的坏字符时，记录模式串的下标值si，并找到坏字符在模式串中，位于下标si前的最近位置xi（若无则记为-1），si-xi即为向后滑动距离。（PS：我觉得加上xi必须在si前面，也就是比si小的条件，就不用担心计算出的距离为负了）。但是坏字符规则向后滑动的步幅还不够大，于是需要好后缀规则。
好后缀
好后缀规则：从后往前逐位比较模式串与主串的字符，当出现坏字符时停止。若存在已匹配成功的子串｛u｝，那么在模式串的｛u｝前面找到最近的｛u｝，记作｛u’｝。再将模式串后移，使得模式串的｛u’｝与主串的｛u｝重叠。若不存在｛u’｝，则直接把模式串移到主串的｛u｝后面。为了没有遗漏，需要找到最长的、能够跟模式串的前缀子串匹配的，好后缀的后缀子串（同时也是模式串的后缀子串）。然后把模式串向右移到其左边界，与这个好后缀的后缀子串在主串中的左边界对齐。
何时使用坏字符规则和好后缀规则呢？首先在每次匹配过程中，一旦发现坏字符，先执行坏字符规则，如果发现存在好后缀，还要执行好后缀规则，并从两者中选择后移距离最大的方案执行。
技巧
1.通过散列表实现，坏字符在模式串中下标位置的快速查询。
2.每次执行好后缀原则时，都会计算多次能够与模式串前缀子串相匹配的好后缀的最长后缀子串。为了提高效率，可以预先计算模式串的所有后缀子串，在模式串中与之匹配的另一个子串的位置。同时预计算模式串中（同长度的）后缀子串与前缀子串是否匹配并记录。在具体操作中直接使用，大大提高效率。
3.如何快速记录模式串后缀子串匹配的另一个子串位置，以及模式串（相同长度）前缀与后缀子串石否匹配呢？先用一个suffix数组，下标值k为后缀子串的长度，从模式串下标为i（0~m-2）的字符为最后一个字符，查找这个子串是否与后缀子串匹配，若匹配则将子串起始位置的下标值j赋给suffix[k]。若j为0，说明这个匹配子串的起始位置为模式串的起始位置，则用一个数组prefix，将prefix[k]设为true，否则设为false。k从0到m（模式串的长度）于是就得到了模式串所有前缀与后缀子串的匹配情况。
实现
仅有坏字符规则：
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
|
function hashMap(needle) {
let hash = [];
for(let i=0; i<26; i++){
hash[i] = -1;
}
for(let i=0; i<needle.length; i++){
let ascii = needle[i].charCodeAt() - 97;
hash[ascii] = i;
}
return hash;
}
function BM(haystack, needle) {
let n = haystack.length;
let m = needle.length;
let hash = hashMap(needle);
let i = 0;
while(i <= n-m) {
let bad = -1;
for(let j = m-1; j>=0; j--){
if(haystack[i+j] !== needle[j]){
bad = j;
break;
}
};
if(bad === -1){
return i;
}
let ascii = haystack[bad+i].charCodeAt() - 97;
i = i + (bad - hash[ascii]);
}
return -1;
}
|
坏字符规则在某些场景下会使si-xi为负值，导致无限循环。如在“aaaaaaa”中匹配”baaaa”。
下面讲好后缀原则加入，完整代码如下：
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
| function suffixAndPrefix(needle) {
let m = needle.length;
let suffix = [];
let prefix = [];
for(let i=0; i<m; i++){
suffix[i] = -1;
prefix[i] = false;
}
for(let i=0; i<m-1; i++){
let j=i;
let k=0;
while(j>=0 && needle[j] === needle[m-1-k]) {
j--;
k++;
suffix[k] = j+1;
}
if(j===-1){
prefix[k]=true;
}
}
return [suffix, prefix];
}
function moveByGoodFix(j, m, suffix, prefix) {
let k = m - 1 - j;
if(suffix[k] !== -1) return j - suffix[k] + 1;
for(let i=j+2; i<=m-1; i++) {
if(prefix[m-i] === true) {
return i;
}
}
return m;
}
function hashMap(needle) {
let hash = [];
for(let i=0; i<26; i++){
hash[i] = -1;
}
for(let i=0; i<needle.length; i++){
let ascii = needle[i].charCodeAt() - 97;
hash[ascii] = i;
}
return hash;
}
function BM(haystack, needle) {
let n = haystack.length;
let m = needle.length;
let [ suffix, prefix ] = suffixAndPrefix(needle);
let hash = hashMap(needle);
let i = 0;
while(i <= n-m) {
let bad = -1;
for(let j = m-1; j>=0; j--){
if(haystack[i+j] !== needle[j]){
bad = j;
break;
}
};
if(bad === -1){
return i;
}
let ascii = haystack[bad+i].charCodeAt() - 97;
let badChar = bad - hash[ascii];
let goodFix = 0;
if(bad<m-1){
goodFix = moveByGoodFix(bad, m, suffix, prefix);
}
i = i + Math.max(badChar, goodFix);
}
return -1;
}
|
KMP算法
PMT数组
KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组。
PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。
next数组
为了编程的方便， 我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。
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
| function next(needle) {
let res = [];
res[0] = -1;
let k = -1;
for (let i = 1; i < needle.length; i++) {
while (k != -1 && needle[i] != needle[k+1]) {
k = res[k];
}
if (needle[i] === needle[k+1]) {
k++;
}
res[i] = k;
}
return res;
}
function KMP(haystack, needle) {
let n = haystack.length;
let m = needle.length;
let nextArray = next(needle);
let j = 0;
for(let i=0; i<n; i++){
while(j>0 && haystack[i] !== needle[j]){
j = nextArray[j-1] + 1;
}
if(haystack[i] == needle[j]) {
j++;
}
if(j == m){
return i-m+1;
}
}
return -1;
}
|
算法比较
| 名称 |
空间复杂度 |
最好时间复杂度 |
最差时间复杂度 |
| BF算法 |
T(1) |
O(nm) |
O(nm) |
| RK算法 |
T(1) |
O(n+m) |
O(nm) |
| BM算法 |
T(2m) |
O(n) |
O(nm) |
| KMP算法 |
T(m) |
O(n+m) |
O(nm) |
学习心得
BF算法是最容易想到的算法，只需要逐个字符去比较，遇到不匹配的字符只需要将主串字符向后移动一位，重复比较即可。
RK算法在BF的基础上，引入了hash值。核心理念是：hash值不相同的两个字符串一定不想等，hash相等的字符串才有可能相等。通过hash值的运算大大降低了字符比较的次数。
BM算法提出坏字符和好后缀的规则，从字符串的尾部开始比较。遇到坏字符则大幅度向后滑动，好后缀规则是记录模式串中前后是否有相同的部分。两个规则中移动距离比较远的，则成为下一次循环比较的开始。
KMP算法在BM算法的基础上，直接先计算模式串的“重复度”即模式串的前后字符是否有相同的部分，匹配到不等的字符就可以把之前比较相等的部分跳过。
BM和KMP都是处理模式串本身，与主串无关。都是为了在下一次比较的时候能够大幅度的向后移动，以提高字符串匹配的速度。
参考资料