字符串匹配

发表于 分类于 本文字数： 3.8k
暴力匹配算法，KMP算法

暴力匹配算法

暴力匹配算法的时间复杂度是O(n*m)，其中n是目标字符串的长度，m是要查找的字符串的长度

1
2
3
4
5
6
7
// 字符串定义
#define MAX_LENGTH 100

typedef struct String {
    char ch[MAX_LENGTH];
    int len;
} String;
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
/**
 * 暴力匹配算法
 * 寻找字符串位置，返回数组下标
 * @param s 目标字符串
 * @param t 要查找的字符串
 * @return t在s中的数组下标
 */
int match_find(String s, String t) {
    // 代表s、t中当前正在对比的字符的指针
    int i = 0, j = 0;

    // 指针越界，循环结束
    while (i < s.len && j < t.len) {
        if (s.ch[i] == t.ch[j]) {
            // 字符匹配成功，指针后移
            i++;
            j++;
        } else {
            // 字符匹配失败，指针位置重置
            i = i - j + 1;
            j = 0;
        }
    }

    // 匹配成功返回下标，匹配失败返回-1
    if (j >= t.len)
        return i - j;

    return -1;
}

KMP算法

KMP算法的时间复杂度是O(n+m)，其中n是目标字符串的长度，m是要查找的字符串的长度，KMP算法的核心是next数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int match_find(String s, String t, const int next[]) {
    // 代表s、t中当前正在对比的字符的指针
    int i = 0, j = 0;

    // 指针越界，循环结束
    while (i < s.len && j < t.len) {
        if (j == -1 || s.ch[i] == t.ch[j]) {
            // 字符匹配成功，指针后移
            i++; j++;
        } else {
            // 字符匹配失败，指针位置根据next数组做出调整
            j = next[j];
        }
    }

    // 匹配成功返回下标，匹配失败返回-1
    if (j >= t.len)
        return i - j;

    return -1;
}

next数组

next数组手算

next数组的计算过程可以看作模式串与自身的匹配过程

例1

1
a b a b a

在如上字符串的next数组中：

第一位元素为-1。第一位元素之前没有字符串，无法取前后缀

1
2
3
4
  ↓
_ a b a b a
↑
 -1

第二位元素为0。第二位元素之前的字符串，前后缀皆为空集，没有相同前后缀

1
2
3
4
   ↓
 a b a b a
 ↑
-1 0

第三位元素为0。第三位元素之前字符串的前缀为{a}，后缀为{b}，没有相同前后缀，当第三位元素匹配失败时，从字符串第一位开始匹配（下标0）

1
2
3
4
     ↓
 a b a b a
 ↑
-1 0 0

第四位元素为1。第四位元素之前字符串的前缀为{a, ab}，后缀为{a, ba}，最长相同前后缀为a，当第四位元素匹配失败时，从字符串第二位开始匹配（下标1）

1
2
3
4
       ↓
 a b a b a
   ↑
-1 0 0 1

第五位元素为2。第五位元素之前字符串的前缀为{a, ab, aba}，后缀为{b, ab, bab}，最长相同前后缀为ab，当第五位元素匹配失败时，从字符串第三位开始匹配（下标2）

1
2
3
4
         ↓
 a b a b a
     ↑
-1 0 0 1 2

其实就是在某个字符之前的所有字符串里，找开头和结尾相同的最长字符串的长度，这个长度可以作为当前字符的next值，当匹配失败时，就可以根据next值来调整指针位置，从而减少匹配次数

例2

1
a b a a b c

在如上字符串的next数组中：

第一位元素为-1。第一位元素之前没有字符串，无法取前后缀

第二位元素为0。第二位元素之前的字符串，前后缀皆为空集，没有相同前后缀

第三位元素为0。第三位元素之前字符串的前缀为{a}，后缀为{b}，没有相同前后缀，从字符串第一位开始匹配（下标0）

第四位元素为1。第四位元素之前字符串的前缀为{a, ab}，后缀为{a, ba}，最长相同前后缀为a，从字符串第二位开始匹配（下标1）

第五位元素为1。第五位元素之前字符串的前缀为{a, ab, aba}，后缀为{a, aa, baa}，最长相同前后缀为a，从字符串第二位开始匹配（下标1）

第六位元素为2。第六位元素之前字符串的前缀为{a, ab, aba, abaa}，后缀为{b, ab, aab, baab}，最长相同前后缀为ab，从字符串第三位开始匹配（下标2）

1
2
 a b a a b c
-1 0 0 1 1 2

例3

1
a b c a b a b

在如上字符串的next数组中：

第一位元素为-1。第一位元素之前没有字符串，无法取前后缀

第二位元素为0。第二位元素之前的字符串，前后缀皆为空集，没有相同前后缀

第三位元素为0。第三位元素之前字符串的前缀为{a}，后缀为{b}，没有相同前后缀，从字符串第一位开始匹配（下标0）

第四位元素为0。第四位元素之前字符串的前缀为{a, ab}，后缀为{c, bc}，没有相同前后缀，从字符串第一位开始匹配（下标0）

第五位元素为1。第五位元素之前字符串的前缀为{a, ab, abc}，后缀为{a, ca, bca}，最长相同前后缀为a，从字符串第二位开始匹配（下标1）

第六位元素为2。第六位元素之前字符串的前缀为{a, ab, abc, abca}，后缀为{b, ab, cab, bcab}，最长相同前后缀为ab，从字符串第三位开始匹配（下标2）

第七位元素为1。第七位元素之前字符串的前缀为{a, ab, abc, abca, abcab}，后缀为{a, ba, aba, caba, bcaba}，最长相同前后缀为a，从字符串第二位开始匹配（下标1）

1
2
 a b c a b a b
-1 0 0 0 1 2 1

next数组计算

next数组的计算过程可以看作模式串与自身的匹配过程，计算next数组的时间复杂度是O(m)，其中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
38
39
40
41
42
43
void get_next(String str, int next[]) {
    /*
     * i、j是指向字符串的两个下标指针，示意如下
     *
     *    i
     *    ↓
     *  _ a b a a b c a b a
     *  ↑
     *  j
     *
     * i 代表当前要计算的值的下标位置
     * j 代表next[i]的候选值
     *
     */
    int i = 0, j= -1;
    // next数组的0位元素无需计算
    next[0] = -1;

    printf("next[%d", next[0]);

    // 循环 length-1 次，计算0位元素之后的后序元素值
    while (i < str.len - 1) {
        if (j == -1 || str.ch[i] == str.ch[j]) {
            /*
             * 如果上下指针指示的字符相同，或者j指针位于起始位，
             * 则两指针向后走，并记当前j下标为第i位的next值
             */
            i++; j++;
            next[i] = j;

            printf(" %d", next[i]);
        } else {
            /*
             * 如果上下指针指示的字符不同，则说明前后缀匹配失败，j回退至next[j]
             * 根据前面的匹配可以知道，next[j]之前的字符前后缀已经匹配成功，
             * 所以可以直接将j回退到next[j]，从next[j]开始继续进行前后缀匹配
             */
            j = next[j];
        }
    }

    printf("]\n");
}

nextval数组

nextval是对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
void get_next(String str, int next[]) {
    int i = 0, j= -1;
    // next数组的0位元素无需计算
    next[0] = -1;

    printf("next[%d", next[0]);

    // 循环 length-1 次，计算0位元素之后的后序元素值
    while (i < str.len - 1) {
        if (j == -1 || str.ch[i] == str.ch[j]) {
            // 字符匹配成功，指针后移
            i++; j++;

            // 计算nextval数组
            if (string.ch[i] == string.ch[j])
                next[i] = next[j];
            else
                next[i] = j;

            printf(" %d", next[i]);
        } else {
            // 如果上下指针指示的字符不同，则j回退
            j = next[j];
        }
    }

    printf("]\n");
}