字符串模式匹配算法——BF和KMP算法

发表于 | 分类于

字符串模式匹配算法——BF和KMP算法

​ 在字符串S中定位/查找某个子字符串P的操作，通常称为字符串的模式匹配，其中P称为模式串。模式匹配有多种算法，这里我先看一下最常见的BF算法和KMP算法。

BF（Brute—Force）算法

​ BF（Brute Force)算法也就是传说中的“笨办法”，是一个暴力/蛮力算法。设串S和P的长度分别为m,n，则它在最坏情况下的时间复杂度是O(m*n)。BF算法的最坏时间复杂度虽然不好，但它易于理解和编程，在实际应用中，一般还能达到近似于O(m+n)的时间度（最坏情况不是那么容易出现的，RP问题），因此，还在被大量使用。

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
/**
 * @param {string} s
 * @param {string} p
 * @return {number}
 */
function strBF(s, p) {
    if (p.length === 0) {
        return 0;
    }
    if (p.length > s.length) {
        return -1;
    }

    for (let i = 0; i<= s.length - p.length; i++) {
        if (s[i] === p[0]) {
            let flag = true;
            for (let j = 1; j < p.length; j++) {
                if (s[i+j] !== p[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
    }
    return -1;
};
KMP算法

​ KMP算法，它是由D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。KMP算法可以在O(m+n)的时间里完成串的模式匹配。它的主要思想是：每当一趟匹配过程中出现字符不匹配时，不需回退i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续匹配过程。

​ 对于KMP算法来说，核心是next数组的计算。next数组中每个值为模式字符串P中每个字符位置的真前缀和真后缀公共部分的最大长度。（ “真前缀”指除了自身以外，一个字符串的全部头部组合；”真后缀”指除了自身以外，一个字符串的全部尾部组合，这里加这个强调是为了区分与我们普通意义上的”前缀“和”后缀“）

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
function getNext (str) {
    let i = 0;
    let j = -1;
    let next = [];
    next[0] = -1;
    while ( i < str.length -1) {
        if (j === -1 || str[i] === str[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

/**
 *
 * @param mainStr
 * @param pStr
 * @returns {number}
 */
function KMP (mainStr, pStr) {
    if (pStr.length === 0) {
        return 0;
    }
    if (pStr.length > mainStr.length) {
        return -1;
    }
    let i = 0;
    let j = 0;
    let next = getNext(pStr);
    while (i < mainStr.length && j < pStr.length) {
        if (j === -1 || mainStr[i] === pStr[j]) {
            i++;
            j++
        } else {
            j = next[j];
        }
    }
    if (j === pStr.length) {
        return i - j;
    }
    return -1;
}
KMP优化

​ KMP算法（未优化版）： next数组表示最长的相同真前后缀的长度，我们不仅可以利用next来解决模式串的匹配问题，也可以用来解决类似字符串重复问题等等。

​ KMP算法（优化版）：优化后的next仅仅表示相同真前后缀的长度，但不一定是最长（称其为“最优相同真前后缀”更为恰当）。此时我们利用优化后的next可以在模式串匹配问题中以更快的速度得到我们的答案（相较于未优化版），但是上述所说的字符串重复问题，优化版本则束手无策。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function getNext (str) {
    let i = 0;
    let j = -1;
    let next = [];
    next[0] = -1;
    while ( i < str.length -1) {
        if (j === -1 || str[i] === str[j]) {
            i++;
            j++;
            if (str[i] !== str[j]) {
                next[i] = j;
            } else {    // 字符相同就继续往前找真前缀
                next[i] = next[j];
            }
        } else {
            j = next[j];
        }
    }
    return next;
}