动态规划之 KMP 算法的实现

发布于:2022-11-09 ⋅ 阅读:(12) ⋅ 点赞:(0) ⋅ 评论:(0)

一、KMP算法的作用

pat表示模式串,长度为Mtxt表示文本串,长度为N。KMP 算法是在txt中查找子串pat,如果存在,返回这个子串的起始索引,否则返回 -1。

 

很明显,pat中根本没有字符 c,根本没必要回退指针i,暴力解法明显多做了很多不必要的操作。

KMP 算法的不同之处在于,它会花费空间来记录一些信息,在上述情况中就会显得很聪明:

因为 KMP 算法知道字符 b 之前的字符 a 都是匹配的,所以每次只需要比较字符 b 是否被匹配就行了。

KMP 算法永不回退txt的指针i,不走回头路(不会重复扫描txt),而是借助dp数组中储存的信息把pat移到正确的位置继续匹配,时间复杂度只需 O(N),用空间换时间

 二、举例说明:

txt1 = "aaacaaab" 
pat = "aaab"
txt2 = "aaaaaaab" 
pat = "aaab"

我们的txt不同,但是pat是一样的,所以 KMP 算法使用的dp数组是同一个。

只不过对于txt1的下面这个即将出现的未匹配情况:

dp数组指示pat这样移动: 

 PS:这个j不要理解为索引,它的含义更准确地说应该是状态(state),所以它会出现这个奇怪的位置,后文会详述。

而对于txt2的下面这个即将出现的未匹配情况:

dp数组指示pat这样移动:

状态机概述 

为什么说 KMP 算法和状态机有关呢?是这样的,我们可以认为pat的匹配就是状态的转移。比如当 pat = "ABABC":

如上图,圆圈内的数字就是状态,状态 0 是起始状态,状态 5(pat.length)是终止状态。开始匹配时pat处于起始状态,一旦转移到终止状态,就说明在txt中找到了pat

比如说如果当前处于状态 2,就说明字符 "AB" 被匹配:

另外,处于某个状态时,遇到不同的字符,pat状态转移的行为也不同。比如说假设现在匹配到了状态 4,如果遇到字符 A 就应该转移到状态 3,遇到字符 C 就应该转移到状态 5,如果遇到字符 B 就应该转移到状态 0:

 具体什么意思呢,举例解释一下。用变量j表示指向当前状态的指针,当前pat匹配到了状态 4:

如果遇到了字符 "A",根据箭头指示,转移到状态 3 是最聪明的:

 如果遇到了字符 "B",根据箭头指示,只能转移到状态 0(一夜回到解放前):

如果遇到了字符 "C",根据箭头指示,应该转移到终止状态 5,这也就意味着匹配完成:

 当然了,还可能遇到其他字符,比如 Z,但是显然应该转移到起始状态 0,因为pat中根本都没有字符 Z:

这里为了清晰起见,我们画状态图时就把其他字符转移到状态 0 的箭头省略,只画pat中出现的字符的状态转移:

 

KMP 算法最关键的步骤就是构造这个状态转移图。要确定状态转移的行为,得明确两个变量,一个是当前的匹配状态,另一个是遇到的字符;确定了这两个变量后,就可以知道这个情况下应该转移到哪个状态。

下面看一下 KMP 算法根据这幅状态转移图匹配字符串txt的过程:

请记住这个 GIF 的匹配过程,这就是 KMP 算法的核心逻辑

为了描述状态转移图,我们定义一个二维 dp 数组,它的含义如下:

dp[j][c] = next
0 <= j < M,代表当前的状态
0 <= c < 256,代表遇到的字符(ASCII 码)
0 <= next <= M,代表下一个状态

dp[4]['A'] = 3 表示:
当前是状态 4,如果遇到字符 A,
pat 应该转移到状态 3

dp[1]['B'] = 2 表示:
当前是状态 1,如果遇到字符 B,
pat 应该转移到状态 2

根据我们这个 dp 数组的定义和刚才状态转移的过程,我们可以先写出 KMP 算法的 search 函数代码:

public int search(String txt) {
    int M = pat.length();
    int N = txt.length();
    // pat 的初始态为 0
    int j = 0;
    for (int i = 0; i < N; i++) {
        // 当前是状态 j,遇到字符 txt[i],
        // pat 应该转移到哪个状态?
        j = dp[j][txt.charAt(i)];
        // 如果达到终止态,返回匹配开头的索引
        if (j == M) return i - M + 1;
    }
    // 没到达终止态,匹配失败
    return -1;
}

三、构建状态转移图

回想刚才说的:要确定状态转移的行为,必须明确两个变量,一个是当前的匹配状态,另一个是遇到的字符,而且我们已经根据这个逻辑确定了dp数组的含义,那么构造dp数组的框架就是这样:

for 0 <= j < M: # 状态
    for 0 <= c < 256: # 字符
        dp[j][c] = next

这个 next 状态应该怎么求呢?显然,如果遇到的字符cpat[j]匹配的话,状态就应该向前推进一个,也就是说next = j + 1,我们不妨称这种情况为状态推进

如果遇到的字符cpat[j]不匹配的话,状态就要回退(或者原地不动),我们不妨称这种情况为状态重启

那么,如何得知在哪个状态重启呢?解答这个问题之前,我们再定义一个名字:影子状态(我编的名字),用变量X表示。所谓影子状态,就是和当前状态具有相同的前缀。比如下面这种情况:

当前状态j = 4,其影子状态为X = 2,它们都有相同的前缀 "AB"。因为状态X和状态j存在相同的前缀,所以当状态j准备进行状态重启的时候(遇到的字符cpat[j]不匹配),可以通过X的状态转移图来获得最近的重启位置

比如说刚才的情况,如果状态j遇到一个字符 "A",应该转移到哪里呢?首先状态 4 只有遇到 "C" 才能推进状态,遇到 "A" 显然只能进行状态重启。状态j会把这个字符委托给状态X处理,也就是dp[j]['A'] = dp[X]['A']

为什么这样可以呢?因为:既然j这边已经确定字符 "A" 无法推进状态,只能回退,而且 KMP 算法就是要尽可能少的回退,以免多余的计算。那么j就可以去问问和自己具有相同前缀的X,如果X遇见 "A" 可以进行「状态推进」,那就转移过去,因为这样回退最少:

当然,如果遇到的字符是 "B",状态X也不能进行「状态推进」,只能回退,j只要跟着X指引的方向回退就行了:

你也许会问,这个X怎么知道遇到字符 "B" 要回退到状态 0 呢?因为X永远跟在j的身后,状态X如何转移,在之前就已经算出来了。动态规划算法不就是利用过去的结果解决现在的问题吗?

PS:对这里不理解的同学建议读读这篇旧文 动态规划设计之最长递增子序列

这样,我们就可以细化一下刚才的框架代码:

int X # 影子状态
for 0 <= j < M:
    for 0 <= c < 256:
        if c == pat[j]:
            # 状态推进
            dp[j][c] = j + 1
        else: 
            # 状态重启
            # 委托 X 计算重启位置
            dp[j][c] = dp[X][c] 

四、代码实现

如果之前的内容你都能理解,恭喜你,现在就剩下一个问题:影子状态X是如何得到的呢?下面先直接看完整代码吧。

public class KMP {
    private int[][] dp;
    private String pat;

    public KMP(String pat) {
        this.pat = pat;
        int M = pat.length();
        // dp[状态][字符] = 下个状态
        dp = new int[M][256];
        // base case
        dp[0][pat.charAt(0)] = 1;
        // 影子状态 X 初始为 0
        int X = 0;
        // 当前状态 j 从 1 开始
        for (int j = 1; j < M; j++) {
            for (int c = 0; c < 256; c++) {
                if (pat.charAt(j) == c) 
                    dp[j][c] = j + 1;
                else 
                    dp[j][c] = dp[X][c];
            }
            // 更新影子状态
            X = dp[X][pat.charAt(j)];
        }
    }

    public int search(String txt) {...}
}

先解释一下这一行代码:

// base case
dp[0][pat.charAt(0)] = 1;

这行代码是 base case,只有遇到 pat[0] 这个字符才能使状态从 0 转移到 1,遇到其它字符的话还是停留在状态 0(Java 默认初始化数组全为 0)。

影子状态X是先初始化为 0,然后随着j的前进而不断更新的。下面看看到底应该如何更新影子状态X

int X = 0;
for (int j = 1; j < M; j++) {
    ...
    // 更新影子状态
    // 当前是状态 X,遇到字符 pat[j],
    // pat 应该转移到哪个状态?
    X = dp[X][pat.charAt(j)];
}

更新X其实和search函数中更新状态j的过程是非常相似的:

int j = 0;
for (int i = 0; i < N; i++) {
    // 当前是状态 j,遇到字符 txt[i],
    // pat 应该转移到哪个状态?
    j = dp[j][txt.charAt(i)];
    ...
}

其中的原理非常微妙,注意代码中 for 循环的变量初始值,可以这样理解:后者是在txt中匹配pat,前者是在pat中匹配pat[1:],状态X总是落后状态j一个状态,与j具有最长的相同前缀。所以我把X比喻为影子状态,似乎也有一点贴切。

另外,构建 dp 数组是根据 base casedp[0][..]向后推演。这就是我认为 KMP 算法就是一种动态规划算法的原因。

下面来看一下状态转移图的完整构造过程,你就能理解状态X作用之精妙了:

状态转移构造过程

至此,KMP 算法就已经再无奥妙可言了!看下 KMP 算法的完整代码吧:

public class KMP {
    private int[][] dp;
    private String pat;

    public KMP(String pat) {
        this.pat = pat;
        int M = pat.length();
        // dp[状态][字符] = 下个状态
        dp = new int[M][256];
        // base case
        dp[0][pat.charAt(0)] = 1;
        // 影子状态 X 初始为 0
        int X = 0;
        // 构建状态转移图(稍改的更紧凑了)
        for (int j = 1; j < M; j++) {
            for (int c = 0; c < 256; c++)
                dp[j][c] = dp[X][c];
            dp[j][pat.charAt(j)] = j + 1;
            // 更新影子状态
            X = dp[X][pat.charAt(j)];
        }
    }

    public int search(String txt) {
        int M = pat.length();
        int N = txt.length();
        // pat 的初始态为 0
        int j = 0;
        for (int i = 0; i < N; i++) {
            // 计算 pat 的下一个状态
            j = dp[j][txt.charAt(i)];
            // 到达终止态,返回结果
            if (j == M) return i - M + 1;
        }
        // 没到达终止态,匹配失败
        return -1;
    }
}

五、本文总结

传统的 KMP 算法是使用一个一维数组next记录前缀信息,实现方法不好理解。本文是使用一个二维数组dp以状态转移的角度解决字符匹配问题,但是空间复杂度仍然是 O(256M) = O(M)。

漫画:什么是KMP算法?