字符串匹配

发表于 更新于 本文字数： 777 阅读时长 ≈ 3 分钟

BF(Brute Force)算法

  • BF是最符合人类直觉的字符串匹配算法，但是主串的下标i经常要往回走，无法利用已匹配信息，效率不够好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int bruteForce(const string& t, const string& p) {
    int i = 0, j = 0;
    // i和j都是非负数，所以可以和无符号直接比较
    while (i < t.size() && j < p.size()) {
        if (t[i] == p[j]) {
            ++i; ++j;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j == p.size())
        return i - j;
    else
        return -1;
}

KMP算法

  • 思想：“利用已部分匹配的信息，保持i指针不回溯，通过修改j指针，让模式串尽量移动到有效的位置”
  • 定义next数组： next[j] = d 表示当 t[i] != p[j] 时，j下一次匹配的位置。注意到，下标从0开始，d值实际上是下标j前的最长前后缀子串的长度
  • 求取next的过程本身就是p串与自己匹配的过程
    1. 当 p[i]==p[j] ，则 p[++i] = ++j
    2. 当 p[i]!=p[j] ，则利用前面已求得的next数组，j=next[j] ；直到无法找到，此时 j=-1 ，自动进入第一个if语句，此时i往后走一步，妙
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
vector<int> getNext(const string& p) {
    int n = p.size();
    vector<int> next(n);
    next[0] = -1;
    int i = 0, j = -1;
    // !!! i < n 则会在下面越界，因为0已经求过了，循环只会进行n-1次
    while (i < n - 1) {
        if (j == -1 || p[i] == p[j]) {
            ++i, ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

int KMP(const string& t, const string& p) {
    vector<int> next = getNext(p);
    int n = t.size(), m = p.size();
    int i = 0, j = 0;
    // !!! j可以为负数，和无符号比较会转换为无符号比较法(南辕北辙)
    while (i < n && j < m) {
        if (j == -1 || t[i] == p[j]) {
            ++i; ++j;
        } else {
            j = next[j];
        }
    }
    if (j == p.size())
        return i - j;
    else
        return -1;
}

KMP之Next优化

  • 比如[ A B A B ]这个串，按照上面所述KMP得到的结果是[-1, 0, 0, 1]，然而，例如匹配的是[ A B A B D E]，在下标为3处失败了，next指导去下标1处继续匹配，但是，下标1和下标3都是B，没有必要再进行比较了。诸如此类的例子还有[ A A A A B]，用上述KMP得到的next是[-1, 0, 1, 2, 3]
  • 方法就是在 ++i, ++j 后加一步判断，本来直接 next[i]=j 但是如果 p[i]==p[j] 则如果以后匹配 p[i] 失败，则匹配 p[j] 肯定也失败啊，所以如果两者相等，直接 next[i] = next[j] 。此时的结果对于[ A B A B ]产生的是[-1, 0, -1, 0]；对于[ A A A A B]产生的是[-1, -1, -1, -1, 3]
  • 加三行代码就行了
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
vector<int> getNext(const string& p) {
    int n = p.size();
    vector<int> next(n);
    next[0] = -1;
    int i = 0, j = -1;
    while (i < n - 1) {
        if (j == -1 || p[i] == p[j]) {
            ++i, ++j;
            if (p[i] == p[j]) // new 
                next[i] = next[j]; // new 
            else // new
                next[i] = j;
        }
        else {
            j = next[j];
        }
    }
    return next;
}

int KMP(const string& t, const string& p) {
    vector<int> next = getNext(p);
    int n = t.size(), m = p.size();
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || t[i] == p[j]) {
            ++i; ++j;
        }
        else {
            j = next[j];
        }
    }
    if (j == p.size())
        return i - j;
    else
        return -1;
}

参考资料

  • 博客园博主：sofu6