KMP子字符串查找算法

KMP算法解决的问题是，在暴力匹配时文本指针不需要回退。基本思想就是当出现不匹配时，就能知晓一部分文本的内容（因为在匹配失败之前它们已经和模式相匹配）。我们可以利用这些信息避免将指针回退到所有这些已知的字符之前。

正文——A B A A A A B A A A A A A A A
模式——B A A A A A
模式—— B A A A A A
模式—— B A A A A A
模式—— B A A A A A
模式—— B A A A A A
模式—— B A A A A A
模式—— B A A A A A

如果是暴力匹配的话，指针需要移动6次，但是可以看出其实不需要移动这么多次。
正文——A B A A A A B A A A A A A A A
模式—— B A A A A A
模式—— B A A A A A

提前判断如何重新开始查找，而这种判断只取决于模式本身。我们通过确定有限状态自动机（DFA）。模式中的每个字符都对应着一个状态，每个此类状态都能转换为字母表中的任意字符。

和模式字符串ABABAC对应的确定有限状态自动机

package chapter5;

/**
 * Created by Blue on 2017/9/4.
 */
public class KMP {
    private String pat;
    private int[][] dfa;

    public KMP(String pat) {
        this.pat = pat;
        int M = pat.length();
        int R = 256;
        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];
            }
            dfa[pat.charAt(j)][j] = j + 1;
            X = dfa[pat.charAt(j)][X];
        }  
    }

    public int search(String txt) {
        int i, j, N = txt.length(), M = pat.length();
        for (i = 0, j = 0; i < N && j < M; i++)
            j = dfa[txt.charAt(i)][j];
        if (j == M) return i - M;
        else return N;
    }

    public static void main(String[] args) {
        String pat = "ABABAC";
        String txt = "BCBAABACAABABACAA";
        KMP kmp = new KMP(pat);
        System.out.println(txt);
        int offset = kmp.search(txt);
        for (int i = 0; i < offset; i++)
            System.out.print(" ");
        System.out.println(pat);
    }
}