算法笔记-KMP算法

整理了一下据说由于过于晦涩难懂而导致某系统程序猿直接在实现字符串匹配的时候直接用暴力算法代替的KMP算法，初看之时确实觉得难以理解，不过经过塞得威客大大一节课的讲解之后，也就慢慢理解了。

大神镇帖

其实在真实的应用中当字母表很大重复字符不多模式串很短（模式串一直都很短吧）的时候，KMP算法并不一定比暴力算法快，但是KMP算法不回退文本指针的特性使得它可以用来处理字符流中的匹配问题。而且如果像0101010111000这样的字母表就是0，1的字符串的话KMP的算法的效率优势就会体现出来。

这门课中的KMP算法是用有限状态自动机（DFA）来实现的，代码很短，但是非常的赞（高德纳大神的智慧熠熠生辉），首先来看一下暴力字符串匹配法：

public class BruteForce {

    public static void main(String[] args){
        String txt = "ABACCABCFT";
        String pat = "FT";
        int a = search(pat, txt);
        if (a == txt.length()){
            System.out.println("Not Found!");
        }else{
            System.out.println("Found: " + a);
        }
    }

    private static int search(String pat, String txt){
        int M = pat.length();
        int N = txt.length();

        for (int i = 0; i <= N - M; i++){
            int j;
            for (j = 0; j < M; j++){
                if (txt.charAt(i+j) != pat.charAt(j)){
                    break;
                }
            }
            if (j == M) return i;//Found
        }
        return N;//Not Found
    }
}

蛮力匹配法非常的简单，稍微有编程基础的人就能够看懂。
然后是用有限状态自动机实现的KMP算法：

public class KMP {
    private final int R;       // the radix
    private int[][] dfa;       // the KMP automoton

    private String pat;        // the pattern string

    public static void main(String[] args) {
        String pat = args[0];
        String txt = args[1];

        KMP kmp1 = new KMP(pat);
        int offset1 = kmp1.search(txt);

        // print results
        System.out.println("text:    " + txt);

        System.out.print("pattern: ");
        for (int i = 0; i < offset1; i++)
            System.out.print(" ");
        System.out.println(pat);

    }

    public int search(String txt) {

        // simulate operation of DFA on text
        int m = pat.length();
        int n = txt.length();
        int i, j;
        for (i = 0, j = 0; i < n && j < m; i++) {
            j = dfa[txt.charAt(i)][j];
        }
        if (j == m) return i - m;    // found
        return n;                    // not found
    }

    public KMP(String pat) {
        this.R = 256;
        this.pat = pat;

        // build DFA from pattern
        int m = pat.length();
        dfa = new int[R][m];
        dfa[pat.charAt(0)][0] = 1;
        for (int x = 0, j = 1; j < m; j++) {
            for (int c = 0; c < R; c++)
                dfa[c][j] = dfa[c][x];     // Copy mismatch cases.
            dfa[pat.charAt(j)][j] = j+1;   // Set match case.
            x = dfa[pat.charAt(j)][x];     // Update restart state.
        }
    }
}

可以看到search方法是几乎一样的，只不过是加了一个DFA，现在来看看DFA是怎么运作的：
在这个实现中，默认字母表是ANSSI字符，所以DFA中有256个小数组，ANSSI表中就256个字符，这也暴露了这种实现的一个缺点：如果是中文字母表或者是其他字特别多的表，那么需要的空间就太多了！
具体讲解这个算法非常麻烦，而且塞得威客大大讲的非常的好，英语好并且爱听课的同学可以去看看他的公开课：
Coursera Algorithm Part II
里相关的视频。
比较喜欢看文字资料的同学可以看一下我啰啰嗦嗦的讲解。

KMP算法是怎么做的

我们知道，在蛮力算法中，在匹配的过程中出现了失配的话，就将模式串的指针重置为0，然后将模式串向前移动一位：

蛮力算法的匹配过程

仔细观察这张图就能发现，这样非常低效，我们能够直观地看到模式串除了第一个是B之外其他的位置上的字母都是A，在位置六失配，所以前面一段必然全是A，我们直接把模式串的起始端移动到六位置就可以了，前面的一步一步移动的操作是可以跳过的，基于这一现象，深入思考，我们可以发现，根据模式串的情况，我们可以推断出来当在某个位置出现失配的时候我们应该怎么去移动模式串,为什么呢？因为当在六位置失配的时候，我们已经知道了第六位之前的五位是匹配的，当我们将模式串向前移动一位再进行匹配的时候，相当于让模式串跟去掉第一个字符并左移一位的自己进行匹配(严格来说不是自己，是自己的一个去掉第一个字符并左移一位的自己的前缀)，失配后再重复这个过程。既然是跟自己的一部分匹配，那我们可以在模式串自身进行这个过程并记录下来各种情况出现的时候该怎么移动，那么，我们就需要构造一个有限状态自动机了。

有限状态自动机

有限状态自动机是一个很简单的概念，先简单看一下它长什么样子：

有限状态自动机的两种表示

先不论代码是怎么写的，说一说背后的思想。

在KMP的字符串匹配的过程中，其实就是一个状态机的状态转换问题，我们以图上的状态机为例。
模式串有多长，就有多少个状态，首先我们是在0状态，然后开始匹配第一个字符，匹配的话，状态机进入第二个状态，开始匹配第二个字符，不匹配的话，根据自动机里存储的转换方式来转换状态。比如在0状态时，被匹配的长字符串的当前字母是A，那我们就根据dfa[A][0]得到我们应该转换到1状态，然后指向被匹配的字符串的指针进1。如果被匹配的长字符串的当前字母是B，那我们就根据dfa[B][0]得到我们应该呆在状态0，然后指向被匹配的字符串的指针进1，然后一步一步地重复这个过程。如果我们前面一直匹配成功的话，我们会成功的从状态0一直转换到状态6，当我们的状态成功达到6的时候，就说明找到匹配了（注意这个过程中指向被匹配字符串的指针并没有发生过回退，我们是通过状态的转换来决定接下来应该从模式字符串的哪一个字符开始与被匹配串的下一个字符进行匹配），匹配结束。
这个过程非常的简单直观，问题在于，我们怎样才能构造出这样的一个状态机。
我们在这个应用中使用了一个二维数组来代表这个状态机，数组的第一个索引是我们在被匹配字符串中所遇到的字符，第二个索引是当前自动机所在的状态，在ANSSI字母表中，字符的总数共256个，所以共有256个子数组，在我们看到的这个案例中，模式串的长度是6，所以共有六个状态，所以每个子数组的长度是六，代表从0到5六个状态。

该怎么构造出这个自动机呢？

过程也非常直观，首先我们一眼就能看出来，当处于零状态的时候，如果我们遇到字母A，说明匹配成功，状态机的状态应该转向状态1，在状态1的时候，如果遇到了字母B，说明匹配再次成功了，状态机的状态应该转换为状态2，按照这个思路，我们可以得到在完全匹配情况下的状态转换情况，于是可以在二维数组中写下这些值。
接下来就是失配状态了，当在状态0的时候，如果发生失配，模式字符串就应该继续停留在状态0，然后将第0个字符跟被匹配串的下一个状态进行比较，所以我们可以将dfa[][0]的未匹配位置都初始化为0，在状态一以及以后的状态是，情况就会稍微复杂一些，因为我们已经不能直接在失配的时候将状态回滚到0了。我们现在要做的事情是这样的，首先用一个指针x指向0状态，然后我们可以直接把0状态里的数值直接拷贝到一状态，因为当在一状态的时候发生不匹配的时候，我们会用已经匹配的去掉首字母前缀进行匹配，结果是空的，因为此时就一个字母匹配，然后我们再用不匹配的那个字母跟模式字符串的第一个字母去匹配，得到模式应该处于的状态，所以可以直接将第一个字母的对应的状态机的这一列拷贝过来，直接拿到结果。然后这个过程是迭代的，也就是说，当我们在第三个字符串失配的时候，我们应该拿模式串的第二个字符和当前文本中的字符跟模式串匹配的到下一步状态机应该在什么状态，我们已经通过x = dfa[pat.charAt(j)][x]得到了使用第二个字符串输入后自动机的状态，也就是说x现在指向的状态已经是输入当前文本字符的前一个状态了，所以我们可以把x指向的那一列直接拷贝到第三个状态里的状态数值，然后我们就可以直接用j = dfa[txt.charAt(i)][j];获取接下来应该处于什么样的状态，这个过程一步一步地向下进行，我们构造出来了一个DFA，然后我们就可以不回退文本指针地进行匹配了。

KMP算法就这么炼成了

理解了有限状态自动机，KMP算法也就可以很容易地写出来了，为了练习一下，笔者做了一下leetcode里的编程练习：
字符串匹配
有兴趣的同学可以去练习一下加深理解。