为什么要KMP

本文以一个非常常见的字符串匹配问题讲述字符串匹配的几种理解角度。即在字符串S(长为N)中找到模式串T(长为M)出现的第一个位置。

首先字符串匹配查找的方法大家都能想到一个暴力解法,复杂度是O(NM)，显然是太慢了的。希望能找到一个O(M+N)的方法，那就是KMP算法

本质是利用子串内部的信息加快检索。

  • 比如当如下不匹配发生时：
  • 暴力枚举法是让T串移动1格，重新枚举
  • 而KMP则是移动4格，因为ABCDAB后缀和前缀有两个相同

next数组法

跳转数组定义

KMP算法需要首先设置一个跳转数组next，其next[i]代表以[0, j-1]区间后缀与前缀最大相同长度。
其本质是 next整体[0, j-1]是后缀与前缀最大相同长度整体向右平移一位，然后首位补-1

i0123456
模式串ABCDABD
next-1000012

根据跳转数组的KMP

KMP算法是一种母串指针不倒退，而去调整模式串位置的检索方法。

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
/* 在 S 中找到 P 第一次出现的位置 */
int KMP(string S, string P, int next[])
{
    GetNext(P, next);

    int i = 0;  // S 的下标
    int j = 0;  // P 的下标，表示成功匹配j个字符
    int s_len = S.size();
    int p_len = P.size();

    while (i < s_len && j < p_len)
    {
        if (j == -1 || S[i] == P[j])  // P 的第一个字符不匹配或 S[i] == P[j]
        {
            i++;
            j++;
        }
        else
            j = next[j];  // 当前字符匹配失败，进行跳转
    }

    if (j == p_len)  // 匹配成功
        return i - j;
    
    return -1; //未找到
}

跳转数组实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* P 为模式串，下标从 0 开始 */
void GetNext(string P, int next[])
{
    int p_len = P.size();
    int i = 0;   // 后缀末尾index
    int j = -1;  // 前缀末尾index
    next[0] = -1;

    while (i < p_len - 1)
    {
        if (j == -1 || P[i] == P[j])  //匹配
        {
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];   //当前缀不匹配时，前缀退回到上一个长度
    }
}

next优化

以上next初始化仍旧存在无用功。比如一下模式串，匹配到最后一个B不同时，未优化的做法是回退到next[5]=1，也就是第一个B的位置，而实际上B已经比较过了，这个B 100%是不符合的，肯定在KMP里调用j=next[j]，所以我们干脆优化数组，如果发现不符合，提前在next数组就初始化好结果，降低KMP运行过程中j=next[j]的调用次数。

i0123456
模式串ABCDABD
next(未优化)-1000012
next(优化)-1000-102
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* P 为模式串，下标从 0 开始 */
void GetNext(string P, int next[])
{
    int p_len = P.size();
    int i = 0;   // 后缀末尾index
    int j = -1;  // 前缀末尾index
    next[0] = -1;
    while (i < p_len - 1)
    {
        if (j == -1 || P[i] == P[j])
        {
            i++;
            j++;
            if (P[i] != P[j])
                next[i] = j;
            else
                next[i] = next[j];  // 既然相同就继续往前找真前缀
        }
        else
            j = next[j];
    }
}

状态机DFA理解

如果难以理解跳转数组，其实还有一种容易理解的实现是借助有限状态机的思想，模式串构成了一个有限状态自动机，共有len(pattern) + 1个状态。
其本质是用DFA去实现前缀指针。
状态的转移是KMP算法可以达到O(len(text))的时间复杂度的关键。如下

穷举模式pat的所有可能情况，将这些情况用状态图表示。其中X记录匹配失败时重启的索引位置。

其代码如下：

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
private final int R;       // the radix
private int[][] dfa;       // the KMP automoton
private String pat;
public build_DFA(String pat) {
    this.R = 256;   //假设字典大小为256
    this.pat = pat;
    //构造pat对应的dfa
    int M = pat.length();
    dfa = new int[R][M];
    dfa[pat.charAt(0)][0] = 1;
    for (int X = 0, j = 1; j < M; j++) {  //X记录匹配失败时的索引位置,j指向pat
        for (int c = 0; c < R; c++) {   //对于匹配失败的情况，直接复制重启状态
            dfa[c][j] = dfa[c][X];
        }
        dfa[pat.charAt(j)][j] = j + 1;           //匹配成功的指向下一个状态
        X = dfa[pat.charAt(j)][X]; //更新重启位置X
    }
}

public int search(String txt) {
    int M = pat.length();
    int N = txt.length();

    int i, j;  //i指向txt，j指向pat
    for (i = 0, j = 0; i < N && j < M; i++) {
        j = dfa[txt.charAt(i)][j];
    }
    if (j == M) return i - M;   //匹配
    return N;                   //不匹配

}

其迭代过程如下：





AC自动机：多个子串匹配

其实对于这种AC自动机的理解一点也不喜欢。

针对一个问题：给一个很长很长的母串 长度为n，然后给m个小的模式串。求这m个模式串里边有多少个是母串的字串。
该问题在搜索引擎内的词频统计、敏感词排除等场景非常常见。

在字典树(trie树)上检索

AC自动机的基础是Trie树。和Trie树不同的是，树中的每个结点除了有指向孩子的指针（或者说引用），还有一个fail指针，它表示输入的字符与当前结点的所有孩子结点都不匹配时(注意，不是和该结点本身不匹配)，自动机的状态应转移到的状态（或者说应该转移到的结点）。fail指针的功能可以类比于KMP算法中next数组的功能。

我们现在来看一个用目标字符串集合{abd,abdk, abchijn, chnit, ijabdf, ijaij}构造出来的AC自动机

检索过程如下（设文本串abchnijabdfk)：

详见代码search(char *st)

构造AC自动机方法

描述

  1. 先构造字典树： 将所有的目标字符串插入到Trie树中，用简单的数组法存储
  2. 然后通过广度优先遍历为每个结点的所有孩子节点的fail指针找到正确的指向。
    每个结点fail指向的解决顺序是按照广度优先遍历的顺序完成的，或者说层序遍历的顺序进行的，也就是说我们是在解决当前结点的孩子结点fail的指向时，当前结点的fail指针一定已指向了正确的位置。详情见buildDFA()函数

过程图示

  • 完成了3层构造，
  • 完成了4层构造
  • 完成了5层构造
  • 完成了6层构造

代码

代码并非直接copy他人博客内的代码，我根据可读性做了一些修改。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <deque>
//#include <queue>
using namespace std;

class Node
{
public:
    Node *fail;
    Node *next[26]; //only lower case
    int cnt; // 以该node为结尾的单词有几个
    int depth;

    Node(Node *_fail = nullptr, int _depth = 0) : fail(_fail), cnt(0), depth(_depth)
    {
        memset(next, 0, sizeof(next));
    }

    ~Node()
    {
        for (int i = 0; i < 26; i++)
        {
            if (next[i] != nullptr)
                delete next[i];
        }
    }
};

//Node* q[10000000];

class AC_automaton
{
public:
    Node *root;

    AC_automaton() : root(new Node(nullptr)) {}

    void insert(char *st)
    {
        Node *p = root;
        int len = strlen(st);
        for (int i = 0; i < len; i++)
        {
            int c = st[i] - 'a';
            if (p->next[c] == nullptr)
            {
                p->next[c] = new Node(root, i + 1);
            }
            p = p->next[c];
        }
        p->cnt++;
    }

    void buildDFA()
    {
        deque<Node *> q;
        q.push_back(root);

        while (!q.empty())
        {
            //判断当前这个节点和其fail节点是否存在相同儿子，如果存在
            Node *curr = q.front();
            Node *fail = nullptr;
            q.pop_front();
            for (int i = 0; i < 26; ++i)
            {
                if (curr->next[i] != nullptr)
                {  //存在相同儿子
                    // 更新从根到当前节点儿子curr->next[i]的fail，
                    q.push_back(curr->next[i]);
                    for (Node *fail = curr->fail; fail != nullptr; fail = fail->fail) // 遍历所有可能的前缀
                    {
                        if (fail->next[i] != nullptr)
                        { //某个前缀相同
                            curr->next[i]->fail = fail->next[i];
                            break;
                        }
                    }
                }
            }
        }
    }

// 统计所有st内模式串匹配的个数，以及每个模式串第一次匹配的位置
    int search(char *st)
    {
        int cnt = 0;
        Node *p = root;
        int len = strlen(st);
        for (int i = 0; i < len; i++)
        {
            int t = st[i] - 'a';
            // 不能再往下时转移到fail节点
            while (p->next[t] == nullptr && p != root)
            {
                p = p->fail;
            }
            p = p->next[t];
            if (p == nullptr) p = root;

            //遍历以当前子树后缀内是否等同其他模式串
            for (Node *tmp = p; tmp != root && tmp->cnt != -1; tmp = tmp->fail)
            {
                if (tmp->cnt > 0) // 匹配了某个模式串
                {
                    cnt += tmp->cnt;
                    // 输出第一次匹配的位置
                    cout << "start:" << (i - tmp->depth + 1) << "\t\tlen:" << tmp->depth + 1 << "\t\tcount:" << tmp->cnt
                         << endl;
                }
                tmp->cnt = -1;
            }
        }

        return cnt;
    }
} AC;

int main()
{
    AC.insert("ababacd");
    AC.insert("ababc");
    AC.insert("ababc");
    AC.insert("babc");
    AC.insert("abab");
    AC.buildDFA();

    std::cout << AC.search("ababacdababcababacd") << std::endl;
    return 0;
}

用AC自动机思想回看next数组

对于AC自动机只有单条pattern的特殊情况，其实next数组 等同于 树上一条链的所有fail指针的数组。
我也按照AC自动机的理解思路写了一版代码，只不过为了节省空间，去掉了字典树。看上去比next数组版本复杂，但实质是一样的。
对应[leetcode `8. Implement strStr()](https://leetcode.com/problems/implement-strstr/)

代码中fails数组代表不同状态下的fail指针指向，0表示root状态

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
 int* fails = nullptr;
int strStr(string haystack, string needle) {
    int n = needle.size();
    if (n ==0)
    {
        return 0;
    }
    
    //build DFA
    fails = new int[needle.size()+1];  //index = state
    memset(fails, 0, sizeof(int) * (needle.size()+1));
    
    fails[0] = -1; //0 = root(start) state, -1 = null state
    
    for (int i=0; i<n; i++)
    {
        int curr = i;
        int curr_next = i+1;
        int fail = fails[i];
        int fail_next = fails[i]+1;
        while (fail != -1)
        {
            if ( needle[fail] == needle[curr])
            {
                fails[curr_next] = fail_next;
                break;
            }
            fail = fails[fail];
            fail_next = fail+1;
        }
    }
    
    // find
    int state = 0;
    for (int i =0; i < haystack.size(); i++)
    {
        if (haystack[i] == needle[state])
        {
            state ++;
            if (state == n)
            {
                delete [] fails;
                return i - n + 1;
            }
        }else
        {
            state = fails[state];
            while (state != -1 && haystack[i] != needle[state] )
            {
                state = fails[state];
            }
            if (state == -1)
                state = 0;
            else state ++;
        }
    }
    
    delete [] fails;
    return -1;
}

小结

我个人还是认为对于KMP AC自动机版本最容易理解，状态机其次，最难的是直接去理解网上广为流传的KMP算法。我只是做个整理和写点自己的理解，其实引用内的博客已经写得详细了。

reference

KMP算法（1）：如何理解KMP
KMP 算法 v_JULY_v
KMP子字符串查找算法
多模字符串匹配算法之AC自动机—原理与实现