KMP字符串匹配算法

2015/11/16 posted in  算法&数据结构

KMP是一种不太常用的字符串匹配算法,但是在某些情况下,依然可以发挥作用,而它的next思想,更是可以应用在别的地方。

这是我第三次总结KMP算法,第一次是在ACM集训后填坑期间,第二次是在学《数据结构》补充笔记的时候,因为三次的目的不同,这次的侧重点应该是KMP算法本身,希望写出来的总结能对周老师和大家有些许帮助。

朴素算法

在说KMP算法前,必然要说朴素算法,也就是我们常用的字符串匹配算法。

假设我们有一个S串和一个T串,我们需要判断S串中是否包含一个T串,或者找到T串首次出现的位置等操作。一般情况下,我们会进行如下的操作:

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        char[] S = scanner.next().toCharArray();
        char[] T = scanner.next().toCharArray();

        boolean isFind = false;
        for(int i = 0;i < S.length;i++){

            isFind = true;
            for(int j = 0, ti = i;j < T.length;j++, ti++){
                
                if(ti == S.length){
                    isFind = false;
                    break;
                }
                
                if(S[ti] != T[j]){
                    isFind = false;
                    break;
                }
            }

            if(isFind){
                break;
            }
        }

        System.out.println(isFind ? "YES" : "NO");
    }
}

当然,如果硬要说这种情况不好还想进行优化的话,可以进行优化的地方还是很多的,KMP便是针对指针回溯进行优化的算法。

什么是指针回溯

如上文的两个for循环,其中的 i,ti 和 j 分别对 S 和 T 串进行位置标记,然后进行比较等操作,我们可以把 i,ti 和 j 看做三个标记指针,而在每一轮的比较中(也就是内循环break前算作一轮比较),ti 和 j 进行不断向后移动进行比较,然而如果比较失败(发现了不同),那么,ti 就会回溯到 i + 1 的位置(当本次内循环结束,再次执行内循环时 i 已经进行了自增操作。),而 j 指针会回溯到 0 (也就是T串的开始位置),然后进行再次比较,以此重复直到找到匹配位置或者外循环结束。

如果看算法流程的话,可以更明显的看出指针回溯。

算法流程

  1. i 指向S串开始
  2. j 指向T串开始,ti 指向和 i 相同的位置
  3. 对 j 指向的字符和 ti 指向的字符判断 相同?执行4:执行6
  4. j 指针后移,ti指针后移
  5. j 或 ti 指向 S 或 T 串的结尾 ? 执行6:执行3
  6. i 自增
  7. i 指向S串的结束?执行8:执行2
  8. 打印结果

改良方向假设

很明显,如果我们可以做到两个指针减少回溯,或者保证一个不回溯,是不是就可以减少无用的匹配。

为了方便说明,我们可以举一个极端的栗子:

对于S串和T串是上图的样子,如果使用朴素算法,在匹配失败的时候,i指针(现在指向S串的第10个元素'a')应该会回溯到S串的第4个元素 'b' 上,而 j 指针,也会从T串的第8个元素'c',回溯到T串的第1个元素'a'上,然后进行重新循环比较。

而我们很明显可以看出来,这并不是最佳方案,最佳方案应该是i指针稳住不动,继续指向第10个元素,而j指针回溯到第1个元素上。因为很明显,i在前10个元素处不会有全匹配。

当然,这是我们已经可以一眼看到全局而能做出的最佳方案,而程序是不可能眼观全局的,但不意味着程序做不出这样的判断。

我们假设程序虽然不知道S串后面是什么样子,但已经知道了 T 串的构造和 T 串与 S 串已经匹配的部分,那么就应该可以做到清楚的知道指向 T 串的 j 指针应该怎么移动而可以避免回溯指向 S 串的 i 指针。

那么,如果上面说的不是神话,则明白 T 串的构造便是实现上述想法的关键。

因此,KMP算法诞生了。

KMP算法

终于讲到正题了,正如上文所说,与朴素算法相比,KMP算法多了对 T 串的构造进行分析,从而诞生了next数组。而next数组,便是整个KMP算法的核心,不仅仅是字符串匹配,在前缀,后缀,循环节判断等方面,next也能发挥重大作用。

next数组的意义

要想清楚什么是next数组,next数组的意义,切入点便是next数组在匹配中起到的作用。

还是这张图,朴素算法的缺点是什么呢,就是说:匹配过的就是做的无用功,不管你匹配多么长,都是按照没匹配过,无情的从开头再来一遍,这就导致了时间的浪费

如果我们匹配过以前的,不再放弃了,而是利用匹配过的信息推导出有用的信息。目的就是:匹配过的 S 串中还有多少直接等于 T 串的 ,假设知道了这个信息,是不是将会节省不少事件。

因此,next中就是保存的匹配过的 S 串中还有多少直接等于 T 串的

假设我们开始匹配的时候i指针指向了S[e],j指针指向T[0],进行了k次比较之后发现不同,也就是比对失败了,我们是不是可以得出结论:S[e,e+k] = T[0,k]

而如果我们的next数组已经记录了匹配过的S串中还有多少直接等于T串的,假设这个值为t,那么是不是也就意味着:S[e',e'+k] = T[0,t]。

如下图所示:

利用意义上的 next 数组得出 kmp 算法

定义: 此字符串的开头到某一位置称为这个字符串的前缀,,从某一个位置到这个字符串的最后位置称为这个字符串的后缀。

于是,我们需要截取所有的前缀来匹配后缀,因为 T 串在匹配时可能会用到各式各样的前缀,我们 next[]数组就是为了,一个前缀一个最大前后缀匹配值。

因此,求next数组的代码就出来了:

private int[] getNext(){
    char[] chars = this.str.toCharArray();
    int len = chars.length;
    int[] next = new int[len + 1];
    int k = -1, i = 0;
    next[0] = -1;

    while(i < len){
        if(k == -1 || chars[k] == chars[i]){
            i++;
            k++;
            next[i] = k;
        }else{
            k = next[k];
        }
    }
    return next;
}

(这是从今天的KMP题目SDUTOJ 2784中直接取出来的一个方法)

有了next数组后,当失配时,固定 i 指针不动,直接利用 T 串的 next 值滑,将我们知道的信息(我们知道到哪里的前缀和后缀相等)再次验证一遍来浪费时间。

那么我们的匹配算法就可以写作下面这个样子:

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        char[] S = scanner.next().toCharArray();
        char[] T = scanner.next().toCharArray();

        boolean isFind = false;
        int j = 0;
        for(int i = 0;i < S.length;i++){
            
            if(j == T.length){

                isFind = true;
                break;
            }
            if(S[i] == T[j]){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }

        System.out.println(isFind ? "YES" : "NO");
    }
}

由两个for循环嵌套变成一个是不是很爽的样子!!

当然,这只是next的常规用法(字符串匹配),而next的灵活用法还有很多(比如刚才说的前缀后缀什么的,还包括SDUTOJ 2784)。

结束语

这篇文章只是KMP总结和next数组的介绍,作为SDUTOJ 2784解题报告的前置技能 _(:з」∠)_。

文中插图/定义引用了王政(@9cai)同学在队期间写的《Kmp 算法引论》(好流弊的名字_),因为Linux下做图片麻烦,也懒得去做图片了。

文章写成仓促,重点放在KMP与朴素算法比较和next的引入上,可能文章中存在些许问题,欢迎指正。

最后,引用我第二次对KMP总结文的内容作为结束语:

  1. 传统算法(朴素算法)最坏情况是O(nm),但一般是在O(n+m),也不是太坏,所以一般没有特殊要求的程序还在用这种算法;
  2. KMP算法在有大量重复的情况下优化明显,对主串较大时比较有效;
  3. next函数还是有缺陷的,比如模式串’aaaab’与主串’aabaaaab’匹配时,用时几乎和朴素算法一样;
  4. 以发展的眼光看问题,其实作为常用算法之一,匹配算法也有发展,KMP已经不是主流。