【蓝桥杯】KMP算法难以理解只能硬背?东哥这个思路让你10分钟彻底掌握

本文阅读 12 分钟
首页 代码,Java 正文

🍊 Java学习:Java从入门到精通总结

KMP 算法(Knuth-Morris-Pratt 算法)是一个著名的字符串匹配算法,效率很高,说实话,有点复杂。

这种高级且常用的算法经常会在各种竞赛 / 面试场景中出现,先给大家说一个真实的例子吧,在我当初校招面试华为sp时,面试官就让我当场写一个KMP算法,大致的题目如下: ​​​​​​​​ img 这个算法是一个比较奇葩的存在,业内流行一句话,当你第一遍没学会掌握kmp时,之后再看就会耗费成倍的精力。不幸的是我第一遍没掌握这个算法,所以当时我是直接把模板给背诵了下来,以一种非正常的方式通过了面试。

之后复盘环节偶然看到了东哥(公众号labuladong)使用动态规划的思路给出的解析,顿感豁然开朗,把之前非常诡异的next数组定义给丢掉了,二维数组的解法不禁让我直呼内行,先整理如下,祝各位蓝桥杯顺利~

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

目前大部分的解析应该是:对pat进行一顿操作之后生成一个next数组,再利用next数组的数据去一顿操作来匹配txt。next数组和txt、pat的前缀后缀有关,很难理解,理解了可能也忘的比较快。我么可以用一个二维数组来减少代码长度,提高可解释性。

1 概述

普通字符串匹配可以用暴力破解来写,具体思路是:从txt起始索引0开始匹配pat,匹配上了则返回起始索引,匹配不上则再从txt索引1处开始匹配,以此类推…

img

KMP 算法的不同之处在于,它会花费空间来记录一些信息,在上述情况中就会显得很聪明。由于pat中根本不存在c字符,所以可以直接跳过这个字符:

img

KMP 算法则不会重复扫描txt,而是借助next数组中储存的信息把pat移到正确的位置继续匹配,用空间换时间。

传统的KMP算法框架如下:

// KMP算法主体逻辑。str是主串,pattern是模式串
public static int kmp(String str, String pattern) { 
    //预处理,生成next数组
    int[] next = getNexts(pattern);
    int j = 0;
    //主循环,遍历主串字符
    for (int i = 0; i < str.length(); i++) { 
        while (j > 0 && str.charAt(i) != pattern.charAt(j)) { 
            //遇到坏字符时,查询next数组并改变模式串的起点
            j = next[j];
        }
        if (str.charAt(i) == pattern.charAt(j)) { 
            j++;
        }
        if (j == pattern.length()) { 
            //匹配成功,返回下标
            return i - pattern.length() + 1;
        }
    }
    return -1;
}
// 生成Next数组
private static int[] getNexts(String pattern) { 
    int[] next = new int[pattern.length()];
    int j = 0;
    for (int i=2; i<pattern.length(); i++) { 
        while (j != 0 && pattern.charAt(j) != pattern.charAt(i-1)) { 
            //从next[i+1]的求解回溯到 next[j]
            j = next[j];
        }
        if (pattern.charAt(j) == pattern.charAt(i-1)) { 
            j++;
        }
        next[i] = j;
    }
    return next;
}
public static void main(String[] args) { 
    String str = "ATGTGAGCTGGTGTGTGCFAA";
    String pattern = "GTGTGCF";
    int index = kmp(str, pattern);
    System.out.println("首次出现位置:" + index);
}

我们可以看到,KMP 算法的难点在于如何计算next数组中的信息?如何根据这些信息快速的移动pat的位置?

首先需要明确一点:计算这个数组,只和pat有关。这样的话KMP算法框架可以如下:

public class KMP { 
    private int[][] dp;
    private String pat;
 
    public KMP(String pat) { 
        this.pat = pat;
        // 通过 pat 构建 dp 数组
        // 需要 O(M) 时间
    }
 
    public int search(String txt) { 
        // 借助 dp 数组去匹配 txt
        // 需要 O(N) 时间
    }
}

这样,当我们需要用同一 pat 去匹配不同txt时,就不需要浪费时间构造dp数组了:

KMP kmp = new KMP("aaab");
int pos1 = kmp.search("aaacaaab"); //4
int pos2 = kmp.search("aaaaaaab"); //4

2 状态机

我们可以认为 pat 的匹配就是状态的转移。比如当 pat = "ABABC"时: img

圆圈内的数字就是状态,状态 0 是起始状态,状态 5是终止状态。开始匹配时 pat 处于起始状态,一旦转移到终止状态,就说明在txt中找到了pat。如果当前处于状态 2,则说明字符 “AB” 被匹配: img

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

img

具体来说,当前 pat 匹配到了状态 4: img

如果遇到了字符 “A”,根据箭头指示,转移到状态 3 : img

如果遇到了字符 “B”,根据箭头指示,转移到状态 0: img

如果遇到了字符 “C”,根据箭头指示,转移到终止状态 5,意味着匹配完成: img

最终的转移状态图可以画成如下的样子: img

构造这个状态转移图,需要两个变量,一个是当前的匹配状态,另一个是遇到的字符;确定了这两个变量后,就可以知道这个情况下应该转移到哪个状态。

如果已经获得了这张转移图,字符串的匹配过程就如下所示:

img

为了描述状态转移图,我们定义一个二维 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;
}

3 生成状态转移图

3.1 基本框架

“要确定状态转移图,必须明确两个变量,一个是当前的状态,另一个是遇到的字符”。dp数组的构建框架就如下:

// 状态
for 0 <= j < M{ 
    // 遇到的字符
    for 0 <= c < 256{ 
        dp[j][c] = next;
    }
}

对于next,如果遇到的字符c和pat[j]匹配的话,状态就应该进入下一个,即 next = j + 1: img

如果遇到的字符c和pat[j]不匹配的话,状态就要回退:

img

如何得到应该回退到的位置是一个问题,不妨定义一个“影子状态”用变量X表示。所谓影子状态,就是和当前状态具有相同的前缀

img

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

如果状态j遇到一个字符 “A”,首先状态 4 只有遇到 “C” 才能推进状态,遇到 “A” 显然只能进行状态回退。状态j会把这个字符委托给状态X处理,也就是dpj = dpX:

img

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

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

img

X永远跟在j的身后,状态X如何转移,在之前就已经算出来了(动态规划 或者 递归的思想)

因此我们可以优化刚刚的计算dp数组的代码:

// 影子状态
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];
        }
    }
}

3.2 生成影子状态

总体框架如下:

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) { ...}
}

其中的初始状态:

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

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

影子状态X是先初始化为 0,然后随着j的前进而不断更新的。

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:length],状态X总是落后状态j一个状态,与j具有最长的相同前缀。

完整过程:

img

4 完整代码

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) { 
        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;
    }
}

核心代码是两个函数中 for 循环的部分

5 总结

在pat匹配txt的过程中,只要明确了「当前处在哪个状态」「遇到的字符是什么」这两个问题,就可以确定应该转移到哪个状态。

dp数组的含义:

dpj = next:当前是状态j,遇到了字符c,应该转移到状态next。

明确了其含义,就可以很容易写出 search 函数的代码。

对于如何构建这个dp数组,需要一个辅助状态X。在构建当前状态j的转移方向时,只有字符pat[j]才能使状态推进(dpj] = j+1);而对于其他字符只能进行状态回退,应该去请教状态X应该回退到哪里(dpj = dpX,其中other是除了pat[j]之外所有字符)。

我们把X初始化为 0,并且随着j的前进进行更新,更新的方式和 search 过程更新j的过程非常相似(X = dpX])。

本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://wangjiawei.blog.csdn.net/article/details/121954131
-- 展开阅读全文 --
安全面试之XSS(跨站脚本攻击)
« 上一篇 07-24

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复