今天看了kmp算法，最开始看得特别混乱，最后终于看明白了，想记录一下。
https://github.com/hym105289/KMP/blob/master/src/KMP.java

1.题目

给定两个字符串str和match，长度分别为N和M。实现一个算法，如果字符串str中含有子串match，则返回match在str中开始的位置，不含有则返回-1.

2.暴力解法

一般匹配字符串时，我们从目标字符串str（假设长度为n）的第一个下标选取和match长度（长度为m）一样的子字符串进行比较，如果一样，就返回开始处的下标值，不一样，选取str下一个下标，同样选取长度为n的字符串进行比较，直到str的末尾（实际比较时，下标移动到n-m）。这样的时间复杂度是O(n*m)。

复杂度O（MN）

 public static int search(String str,String match){
        int N=str.length();
        int M=match.length();
        for (int i = 0; i <= N-M; i++) {
            int j=0;
            for (j = 0; j < M; j++) {
                if (str.charAt(i+j) != match.charAt(j)) {
                    break;
                }
            }
            if (j == M) {
                return i;
            }
        }
        return -1;
    }

回溯i指针

public static int search3(String pat, String txt) {
        int j, M = pat.length();
        int i, N = txt.length();
        for (i = 0, j = 0; i < N && j < M; i++) {
            if (txt.charAt(i) == pat.charAt(j))
                j++;
            else {
                i -= j;
                j = 0;
            }
        }
        if (j == M)
            return i - M; // found
        else
            return N; // not found
    }

3.KMP

看一下暴力比较坏的情况

image.png

橙色部分代表相同的子串

public static int getIndex(String str, String pat){
        if (str == null || pat == null || str.length() <pat.length() || pat.length() <1) {
            return -1;
        }
        char[] s=str.toCharArray();
        char[] p=pat.toCharArray();
        int si=0,pi=0;
        int[] next=getNextArr(p);
        while (si<s.length&&pi<p.length) {
            if(s[si] == p[pi]){//字符串匹配则两个指针不断向前移动
                si++;
                pi++;
            }
            else if (next[pi] == -1) {//和模式字符串的第一个字符不匹配，则指向s的字符串向前移动
                si++;
            }else {
                pi=next[pi];   //匹配失败，则重新定位模式串的该匹配字符
            }
        }
        return pi == p.length ? si-pi:-1;
    }

如何快速得到模式字符串pat的nextArr数组，并且复杂度是O(m)？
pat=abaabcac
1.对于nextArr[0]而言，由于它之前没有字符，所以规定nextArr[0]=-1;
2.对于nextArr[1]而言，由于它之前只有一个字符，所以一定没有匹配的前缀子串和后缀子串，nextArr[1]=0；
3.当下标pos>1时求解过程如下：
①从左到右依次求解nextArr数组，先求nextArr[0],nextArr[1],nextArr[2]....最后求nextArr[m-1]，这说明当我们求nextArr[i]时，其实nextArr[i-1]已经求好了，我们已经知道B处之前字符串的前缀子串和后缀子串的最大匹配区域。

橙色部分表示相同的子串

红框分别代表匹配最大的前缀子串和后缀子串

C之前的最长前缀和后缀匹配区域是n和m

m区域和n区域分别是字符C之前的字符串的最长匹配的后缀与前缀区域，这是通过next[cn]确定的，我们可以根据图示看到相同颜色的代表匹配的字符串，那么一定可以在字符B之前的最长匹配的后缀字符串中找到和m区域相同长度的m'区域。，接下来比较字符D和字符B是否相同？
1）D==B，nextArr[i]=nextArr[cn]+1;
2 ) D != B,继续往前跳到字符D，然后重复类似的过程，每次跳一步都会有一个新的字符和B进行比较，如果相等，则nextArr[i]就能够确定。
④ 如果向前跳到最左的位置，即pat[0]的位置，nextArr[0]==-1,则说明字符A之前的字符不存在匹配的前缀和后缀子串，nextArr[i]=0；

public static int[] getNextArray(char[] pat){
        if (pat.length==1) {
            return new int[]{-1};
        }
        int[] next=new int[pat.length];
        next[0]=-1;
        next[1]=0;
        int pos=2;
        int cn=0;//注意cn总是记录着next[pos-1]的值
        while (pos<next.length) {
            if (pat[pos-1]==pat[cn]) {
                next[pos++]=++cn;
            }else if (cn>0) {
                cn=next[cn];
            }else {
                next[pos++]=0;
            }
        }
        return next;
    }