KMP算法的DFA解法

发表于 | 分类于

简单说一下，KMP是一个时间复杂度O（n+m）的字符串匹配算法，网上也有很多其他的解法，比如next数组的解法，推荐看这里

匹配的思路

DFA：确定有限自动状态机
以下是ABABAC的对应的DFA：
这里写图片描述

1.假设文本为txt，待匹配的子串为pat。

2.未匹配是状态0，此时如果条件A（匹配到了txt的字符‘A‘），会到状态1，如果是条件B、C或其他的条件，还是状态0。如果经历了匹配ABABA之后到达状态5，再匹配C到达状态6，即停止状态，也就是匹配成功。

3.很明显，dfa[][]是一个二维数组,dfa['A'][3]就是在状态3时，下一个条件是A时，要跳转到哪一个状态。

4.匹配的过程就是：不断的用txt的字符 + 当时的状态去dfa取值，直到状态6 or txt匹配到最后一个字符，结束。

5.匹配过程中，txt的字符是一个一个往后取，不会回溯，只是状态一直在变化，即本次使用的是上一次匹配后的状态，不会回溯，正是KMP算法相对于暴力解法的优势。

DFA数组的构建

上边的思路如果理解了，那么剩下的问题就是如何构建dfa[][]，当然这也是难点。dfa[][]的元素分为两类：1，匹配成功；2，匹配失败。

1.匹配成功
初始可确定的状态为：
dfa[pat[0]][0] = 1;
即在状态0匹配到子串的第一个字符，到达状态1；
dfa[pat[1]][1] = dfa[pat[0]][0] + 1

2.匹配失败
初始的第一列，即状态0时，匹配失败应该还是状态0，也就是除上述dfa[pat[0]][0] = 1外，其他都为状态0。
那么状态j时，匹配失败：（模拟回溯）
假设此时匹配到c = txt[i]，然后查找dfa找到跳转到哪个状态，那么txt[i-j…i-1]这部分与pat[0…j-1]这部分是匹配的。因为i-j为起始而整体不匹配，所以pat要右移一位，所以txt[i-j]舍弃了，不用比较了，也就是在状态j遇到条件c的要跳转的状态，txt[i-j+1 … i-1] == pat[1 … j-1]。
引入一个状态指示数组X，X[j]是指正确输入p[1…j-1]后进入的状态，输入p[1…j-1]c后进入的状态就是dfa[c][X[j]]（在X[j]状态时输入c），即dfa[c][j]=dfa[c][x[j]]。
X[j+1]为正确输入p[1…j]后进入的状态，即正确输入p[1…j-1]p[j]后进入的状态，也就是在X[j]状态时输入p[j]时进入的状态，就是dfa[pat.charAt[j]][X[j]]，即递推公式为：X[j+1]=dfa[pat.charAt[j]][X[j]]，而X[0]手动初始化为0。
故有：

1
2
3
4
5
6
7
8
9
dfa[pat[0]][0] = 1;
    int X = 0;
    for (j = 1; j < M; ++j){
        for(i = 0; i < R; ++i) {
            dfa[i][j] = dfa[i][X];
        }
        dfa[pat[j]][j] = j + 1; //匹配成功
        X = dfa[pat[j]][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
32
33
34
35
36
37
38
39
40
41
int test_jp_search() {
    int index = jp_search("BCBAABACAABABACAA", "ABABAC");
    printf("%d\n", index);
    return 0;
}

int jp_search(char *txt, char *sub)
{
    int M = (int)strlen(sub);
    int R = 256;
    //二维数组定义并初始化
    int dfa[R][M];
    int i = 0, j = 0;
    for (i = 0; i < R; ++i) {
        for (int j = 0; j < M; ++j) {
            dfa[i][j] = 0;
        }
    }

    dfa[sub[0]][0] = 1;
    int X = 0;
    for (j = 1; j < M; ++j){
        for(i = 0; i < R; ++i) {
            dfa[i][j] = dfa[i][X];
        }
        dfa[sub[j]][j] = j + 1; //匹配成功
        X = dfa[sub[j]][X]; //更新重启状态
    }


    int N = (int)strlen(txt);
    for (i = 0, j = 0; i < N && j < M; ++i){
        j = dfa[txt[i]][j];
    }
    
    if (j == M) {
        return i - M;
    } else {
        return M;
    }
}

ps：感觉还是有点乱，回头再整理一下思路

参考：
1.《算法》第四版
2.链接

显示 Gitment 评论