字符串匹配算法

Posted on Edited on

问题引入

有一个长字符串string，现在需要在该字符串中查找到一个特定短字符串pattern，并返回其位置。

上述问题为经典的字符串查找问题，这类问题数据算法的基础问题，应当熟记解决方法。

Brute-Force算法

最简单的方案就是分别对string和pattern的每个位置进行依次比较。这样就会产生两个循环体分别对string和pattern进行遍历，很容易得出时间复杂度为string长度的二次幂。

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
boolean match = false;
int index = -1;
for (int i = 0; i < source.length(); i++) {
    for (int j = 0; j < pattern.length(); j++) {
        if (source.charAt(i + j) != pattern.charAt(j)) {
            break;
        }
        if (j == pattern.length() - 1) {
            match = true;
            index = i;
        }
    }
    if (match) {
        break;
    }
}

KMP算法

KMP算法是经典的字符串匹配的改进算法。该算法利用pattern的最大重复子串长度表来减少循环次数。

最大重复子串长度表，即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
/**
 * eg. A B C A B D
 *    -1 0 0 0 1 2
 * @param pattern pattern string
 * @return next table of pattern string
 */
private int[] calculateNext(String pattern) {
    int[] next = new int[pattern.length()];

    int j = 0;
    for (int i = 0; i < next.length; i++) {
        if (i < 2) {
            next[i] = i - 1;
            continue;
        }

        if (pattern.charAt(j) == pattern.charAt(i - 1)) {
            next[i] = j + 1;
            j++;
        } else {
            j = 0;
            next[i] = j;
        }
    }

    return next;
}

只看代码可能难于理解，我们来看next表的计算意义。

pattern的子串 前缀 后缀 最大重复子串长度
A 无 无 0
AB A B 0
ABC A，AB C，BC 0
ABCA A，AB，ABC A，CA，BCA 1
ABCAB A，AB，ABC，ABCA B，AB，CAB，BCAB 2
ABCABD A，AB，ABC，ABCA，ABCAB D，BD，ABD，CABD，BCABD 0

很明显，next表来自于最大重复子串长度表整体后移一位，并在第一位补-1。到这里，也就清楚了，KMP算法就是利用pattern的重复部分来减少查找的循环次数。

通过next表来进行匹配的核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int i = 0;
int j = 0;
while (i < source.length() && j < pattern.length()) {
    if (source.charAt(i) == pattern.charAt(j)) {
        i++;
        j++;
    } else {
        j = next[j];
        if (j < 0) {
            i++;
            j++;
        }
    }
}

if (j == pattern.length()) {
    return i - pattern.length();
} else {
    return -1;
}

通过代码应该很容易就能看出来，循环次数只与string的长度有关，KMP算法的时间复杂度为string长度的一次幂。也就是说，next表的结果指导了在匹配时pattern的移位长度。如果pattern没有任何重复的子串，KMP算法也将会退化为Brute-Force算法。