DAY 45 leetcode 28的kmp算法实现

KMP算法的思路

例：

文本串：a a b a a b a a f

模式串：a a b a a f

两个指针分别指向上下两串，当出现分歧时，并不将上下的都重新回退，而是利用“next数组”获取已经比较过的信息，上面的指针不动，而下面的回退到第n个

如：

                              i    指向b

文本串：a a b a a b a a f

模式串：a a b a a f

                     j<---- j    指向f

两者发生冲突，此时将j回退到模式串的第三个元素

然后重新开始同时前进，开始比对

next数组

可以注意到上述思路中最重要的是next数组，究竟如何求出next数组，为什么要回退到指定的位置

定义：next数组中，每个元素的值是，该模式串中对应下标的字符，所对应字符串（即从第一个元素到它自己）的最长相等前后缀的长度。

前后缀

前缀，不包含最后一个字符的所有子串；

后缀，不包含第一个字符的所有子串

如模式串 a a b a a f

next[0]=0;

next[1]=1; //aa这个字符串，对应的前缀为a 后缀为a 相等，且长度为1

next[2]=0; //aab前缀为 a,aa；后缀为ab，b，没有相等的，则为0

next[3]=1; //aaba前缀为 a,aa,aab;后缀为aba,ba,a， a==a，长度为1

next[4]=2; //aabaa前缀为 a,aa,aab,aaba;后缀为abaa,baa,aa,a,  aa==aa, 长度为2

next[5]=0; //aabaaf前缀为a,aa,aab,aaba,aabaa;后缀为abaaf,baaf,aaf,af,f, 没有相等的，为0

如何移动j指针 以及为什么 

依然拿这个举例：

                                 i    指向b

   文本串：a a b a a b a a f

   模式串：a a b a a f

next数组：0 1 0 1 2 0

                        j<---- j    指向f

当两者发生冲突时，我们希望重新比较的次数越少越好，所以需要寻找以及匹配过的字符串，我们将j回退到第next[j-1]个数（即j的前一个）。

为什么呢？

直到f和b才不相同，也就是说之前的都是一一对应的，那么我们将模式串整体移动多少格能“不浪费”已经比对过的结果呢？就是next[j-i]。因为next数组中记录的是最长公共前后缀的长度，而next[j-i]等于2说明，f的前两个和从零开始的头两个字符是完全相等的，而已经说过“一一对应”，说明f的前两个和文本串的此时i指针的前两个是完全相等的，那么可以省去这两步的比较，将j回退到第三个，再开始比较。

求next数组的代码实现

    public static int[] getNext(String s) {int[] arr = new int[s.length()];arr[0] = 0;int j = 0;for (int i = 1; i < arr.length; i++) {//如果j和i对应字符不相等，那么将j移动到arr[j-1]的位置while (j > 0 && s.charAt(j) != s.charAt(i)) {j = arr[j - 1];}//如果相同，j先往前移动一格，再将arr[i]赋值if (s.charAt(j) == s.charAt(i)) {j++;arr[i] = j;}}return arr;}

j有两个作用，一个是在数组中代表最长公共前后缀长度，另一个则是指示位置。

如当s.charAt(j) == s.charAt(i)时，意味着第i处的公共前后缀长度还可以加1，则此时将j自增后赋值给arr[i]，同时还将j往前移动了一格

KMP的代码实现

class Solution {public int strStr(String haystack, String needle){int[] next=getNext(needle);if (needle.length() == 0) {return 0; // 如果needle为空字符串，根据定义返回0}//i指向文本串int j=0; //指向模式串for (int i = 0; i < haystack.length(); i++) {while (j > 0 && needle.charAt(j) != haystack.charAt(i)) j = next[j - 1];//不等则一直移动j指针if (needle.charAt(j) == haystack.charAt(i)) j++;if (j == needle.length()) return i - needle.length() + 1;}return -1;}//反转指定位置的函数public static int[] getNext(String s) {int[] arr = new int[s.length()];arr[0] = 0;int j = 0;for (int i = 1; i < arr.length; i++) {//如果j和i对应字符不相等，那么将j移动到arr[j-1]的位置while (j > 0 && s.charAt(j) != s.charAt(i)) {j = arr[j - 1];}//如果相同if (s.charAt(j) == s.charAt(i)) {j++;arr[i] = j;}}return arr;}}