KMP算法

KMP主要应用在字符串匹配的场景中，其思想是当出现字符串不匹配的情况时，可以知道一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

next数组

next数组是一个前缀表，或者说是前缀表的某种变形。

为了讲清楚next数组的含义，先明确字符串的前缀、后缀的概念

1.前缀：含首字符不含尾字符的所有子串； 2.后缀：含尾字符不含首字符的所有字串。

next[i]：记录下标i(包含i)之前的字符串最长相同前后缀的长度

举例：

1. 如"aa" 前缀只有"a",后缀也只有"a",其最长相同前后缀的长度为1；("a",单个字符不符合前后缀定义，故其最长相同的前后缀的长度为0）
2. 如"aab" 前缀有"a" "aa",后缀有"ab" "b",没有相同的子串,故其最长相同前后缀的长度为0；
3. 如"aaba" ,其最长相同前后缀的长度为1；
4. 如"aabaa" ,其最长相同前后缀的长度为2；
5. 如"aabaaf" ,其最长相同前后缀的长度为0；

所以，字符串"aabaaf"对应的next数组，为{0，1，0，1，2，0};

next数组的任务是当前位置匹配失败后，找到之前已经匹配过的位置再重新匹配，即在某个字符失配时，next数组会指明下一步匹配时模式串应该跳到哪个位置。

KMP算法将O（m*n）字符串暴力匹配算法，降为O（m+n）的算法，m、n分别是模式串和文本串的长度。

KMP例题--> leetCode 28.实现strStr()

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

 

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

/**
  *代码实现：
  */
  public int strStr(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;
        int [] next = new int[needle.length()];
        getNext(needle,next);
        //匹配过程
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
                return (i - needle.length() + 1);
            }
        }
        return -1;
    }
    //KMP ---> next[]
    private void getNext(String s,int[] next) {
    	//j指向前缀的起始位置，i指向后缀的起始位置
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }