KMP(字符串匹配)

KMP算法是一种高效的字符串匹配算法。通常,在求两个字符串是否匹配是,都是枚举一个字符串的开头与另一个字符串匹配, 假如 A 串长度为 n , B 串长度为 m , 那么这种方法的复杂度是 O(nm)的。而KMP能在O(n)的时间内完成。

【KMP思想】

如图,假设有A,B两个字符串要求匹配,当匹配到A[i]、B[j]时,A[1..i-1]与B[1..j-1]完全匹配,但A[i]!=B[j]。通常,遇到这种情况,都是再枚举开头,重新进行匹配,但是这会浪费很多时间。仔细观察,发现B串的a部分与b部分完全相同,那么可以适当减少j的值(相当于把B串往后移动),那么匹配便可以继续进行。如下图。

显而易见,j减少的多少与A无关,只与B有关。 我们完全可以预处理出这样一个数组 next[j], 表示当匹配到 B 数组的第 j 个字母而第 j +1个字母不能匹配了时, 新的 j 最大是多少。 next[j] 应该是所有满足 B[1..k]= B[ j- k+1... j]的k (k < j) 的最大值。

于是容易得出KMP的代码:


1
2
3
4
5
6
7
8
9
void KMP()  {
    int j = 0;
    for (int i = 1;i <= m; i++)  {
        while (j && b[i] != a[j + 1]) j = next[j];
        if (b[i] == a[j + 1]) ++j;
        if (j == n)
            j = next[j];
    }
}

最后的 j=next[j]是为了让程序继续做下去, 因为我们有可能找到多处匹配。

那么next数组要怎么求呢?

假设我们现在已经求得next[1]、next[2]、……next[i],分别表示长度为1到i的字符串的前缀和后缀最大公共长度,现在要求next[i+1]。

  1. 如果位置i+1和位置next[i+1]处的两个字符相同(下标从零开始),则next[i+1]等于next[i]加1。
  2. 如果两个位置的字符不相同,我们可以将长度为next[i]的字符串继续分割,获得其最大公共长度next[next[i]],然后再和位置i的字符比较。这是因为长度为next[i]前缀和后缀都可以分割成上部的构造,如果位置next[next[i]]和位置i的字符相同,则next[i+1]就等于next[next[i]]加1。如果不相等,就可以继续分割长度为next[next[i]]的字符串,直到字符串长度为0为止。

怎么这个预处理过程跟前面的 KMP 主程序这么像呢? 其实, KMP 的预处理本身就是一
个 B 串“自我匹配” 的过程。


1
2
3
4
5
6
7
8
9
void Find_next()  {
    int j = 0;
    next[1] = 0;
    for (int i = 2;i <= n; i++)  {
        while (j && a[j + 1] != a[i]) j = next[j];
        if (a[j + 1] == a[i]) j++;
        next[i] = j;
    }
}

最后为什么KMP的代码会是O(n)的呢?

我们从上述程序的 j 值入手。 每一次执行 while 循环都会使 j减小( 但不能减成负的) , 而另外的改变 j 值的地方只有一处。 每次执行了这一处, j 都只能加 1; 因此, 整个过程中 j 最多加了 n 个 1。 于是, j 最多只有 n 次减小的机会(j 值减小的次数当然不能超过 n , 因为 j 永远是非负整数) 。 这告诉我们, while 循环总共最多执行了 n 次。 按照摊还分析的说法, 平摊到每次 for 循环中后, 一次 for 循环的复杂度为O(n)
整个过程显然是O(n) 的。 这样的分析对于后面next数组预处理的过程同样有效, 同样可以得到预处理过程的复杂度为 O(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
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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

const int N = 1e6 + 10;

struct io  {
    io()  {
        freopen("KMP.in", "r", stdin);
        freopen("KMP.out", "w", stdout);
    }
    ~io()  {
        fclose(stdin);
        fclose(stdout);
    }
}TEXT;

char a[N], b[N];
int next[N], n, m, ans;

void Find_next()  {
    int j = 0;
    next[1] = 0;
    for (int i = 2;i <= n; i++)  {
        while (j && a[j + 1] != a[i]) j = next[j];
        if (a[j + 1] == a[i]) j++;
        next[i] = j;
    }
}

void KMP()  {
    int j = 0;
    for (int i = 1;i <= m; i++)  {
        while (j && b[i] != a[j + 1]) j = next[j];
        if (b[i] == a[j + 1]) ++j;
        if (j == n)  {
            ans++;
            j = next[j];
        }
    }
}

int main(void)  {
   
    scanf("%s%s", a, b);
    n = strlen(a);
    m = strlen(b);
    for (int i = n;i >= 1; i--) a[i] = a[i - 1];
    for (int i = m;i >= 1; i--) b[i] = b[i - 1];
    a[0] = ' ';
    b[0] = ' ';
    Find_next();
    KMP();
    cout << ans;
   
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注