看了好久的kmp算法，我终于懂了，感动。讲到字符串匹配，最傻瓜的做法就是暴力破解。大神们自然是不屑于这种做法，于是创造出一个叫做KMP算法来简化原本的暴力方法。

先附上两个博主的博客，我是看了这个之后才明白next数组是干嘛的：https://blog.csdn.net/qq_37568658/article/details/79313639
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
1.首先要了解一个东西：前缀、后缀、PMT（ Partial Match Table 部分匹配表，即一个字符串中最长的相同的前后缀长度）
前缀：从第一个位置到倒数第二个位置所有字符按顺序组合起来的字符串
后缀：从第二个位置到倒数第一个位置所有字符按顺序组合起来的字符串
比如有个字符串是这样的：ABCDAB，字符串长度为6，字符串中每个字符的index为0-5
即


前缀跟后缀会跟着你关注的字符长度而改变
比如现在我们关注的是0-4的字符，此时的字符串是ABCDA，它的前缀是{A，AB，ABC，ABCD}，后缀是{BCDA，CDA，DA，A}，此时在这两个集合中，我们只找到它们的共同字符串”A”，所以此时ABCDA的PMT为1。
又ABCDAB的前缀{A，AB，ABC，ABCD，ABCDA}，后缀{BCDAB，CDAB，DAB，AB，B}，共同字符串为”AB”，此时PMT为2

PS：注意前缀集合是从第一个开始，然后慢慢添加后面的字符组合起来的字符串，后缀是从第二个到最后一个字符组合起来的字符串，再慢慢减掉前面的字符。
研究PMT有什么意义呢？
还记得如果是暴力破解的话，我们每次比较都是一个一个后移来比较，如下图


从头开始比较时，发现ptr串中的’E’跟主串中的’F’是不一样的，按照以往，我们会把模式串往后挪一个位置，即让ptr从str[1]开始比较，如下图，此时是比较str[1]和ptr[1]

但是聪明的大神们看出了规律，说既然前面都已经比较过了，那么可能会有一些帮助。按照这个思路，我们来看下ptr中的”ABCABF”和str中的”ABCABE”，其中它们的重合部分是”ABCAB”
运用一下刚刚的前后缀知识，我们可以写出”ABCAB”的PMT分别是：{0，0，0，1，2}，对应了字符串”A”,”AB”,”ABC”,”ABCA”,”ABCAB”。
接下来，我们可以把ptr移到3。为什么呢，因为”ABCAB”中的前两个跟后两个是相同的，而后两个在刚刚的第一次比较中是能够与str匹配的，所以我们就直接从那个位置再进行一次匹配比较

然后，Jake Boxer作者就直接给出了一个计算公式：跳过长度=匹配到的字符串长度-PMT，运用到上面的例子就是5（ABCAB的长度）-2（ABCAB）=3，所以要从index=0跳到index为0+3= 3

又比如这种匹配的字符串中没有最长前后缀


匹配的字符串是”ABCDE”，长度为5，PMT为0，即index = 0+(5-0)= 5

而这个所谓的PMT则是经常看到的next数组
在”ABCDAB”中，它对应的next数组是

2.终于到了重点，求next数组。这是一个我一直都不懂，然后反复的看代码和看博客，一步步想清楚后，我终于明白了代码是怎么肥事了！
附上我看得比较懂的代码的博客：https://blog.csdn.net/f1033774377/article/details/82556438
这个博主的意思就是，在求一个字符串的PMT时，先从倒数第二个的PMT看起，看看在之前的基础上加上最后一个后，能不能也继续匹配下去，如果能，那就是next[i] = next[i-1]+1，不行的话咧，那就再看看匹配了的前缀中，会不会剪短后，跟短一点的后缀匹配呢？
ok我们来看一下代码解释，附上”abaabbabaab”的PMT

首先要明白的是F[i]表示的是：0~i中，最长相同前后缀中的前缀字符串最后一个位置，把F[i]+1就是相同前后缀的长度了。比如说上面的字符串，最长相同前后缀是abaab，所以F[10] = 4，因为”abaab”中最后一个b在字符串string中的位置是4，所以最长相同前后缀的长度就是4+1=5了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
String string = "abaabbabaab";
char[] B = string.toCharArray();
int m= B.length;
int[] F = new int[m];
F[0] = -1;
for (int i=1;i<m;i++){
	int j=F[i-1];
	while ((B[j+1]!=B[i])&&(j>=0))
		j=F[j];
	if (B[j+1]==B[i])
		F[i]=j+1;
	else
		F[i]=-1;
}

ok，所以把F[0] = -1的意思也比较清楚，就是没有匹配嘛。
从for循环开始，很明显这是要遍历整个字符串。
然后是 int j = F[i-1]; 为什么j要=F[i-1]，因为要在原来的基础上看看能不能继续匹配下去。
先看if…那里，假设现在i = 10（最后一个字符b），从上表可以得出F[9]是3，所以说现在j=3。F[9]=3的意思就是说，前0~9中的最长相同前后缀有4个，即”abaa”，而”3”代表的就是前缀中最后一个index是3的’a’，PMT=4。那么现在B[10]会不会跟前缀的下一位即B[5]也相同呢？如果相同，那就是直接+1，所以B[10]=4。这就是在原来的基础上继续匹配下去。
如果不同呢，那我们就剪短前缀再来看呗。啥意思呢？
来看一下while到else那里。while中的那句j = F[j]，为什么要这样呢？


我们直接看F[6]是怎么得到的。根据代码，i此时是6，那么j = F[6-1] = F[5] = 1。while比较B[1+1] = B[2] = ‘b’,B[6] = ‘a’，不相等，这时候发现在前面的最长相同前后缀”aa”上不能再继续添加，ok那就剪短，也就是进入while里面。j = F[1] = 0。再进行一次比较B[0+1]=B[1] = ‘a’，B[6] = ‘a’，跳出while循环，直接来到了if语句，则F[6] = 0+1=1，结束。

终于全部讲完，接下来可以通过去leetcode写一下这道题的解法，来验证自己写的KMP算法有没有问题:https://leetcode-cn.com/problems/implement-strstr/

以下是自己的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class Main {
    public static void main(String[] args) {
       
       String str = "hello";
       String ptr = "lo";
       
       System.out.println(strStr(str, ptr));
       
       
    }
   public static int KMP(String haystack, String needle) {
        if (needle.isEmpty()) {
          return 0;
        }
        char[] A = haystack.toCharArray();
       char[] B = needle.toCharArray();
       int i = 0, j=0;
       int index = -1;       
       int s = 0; //保存str是从哪个index开始比较的  
       while (i<A.length && j<B.length) {
           //当两个字符串中的字符相同时
           if (A[i] == B[j]) {   
               //判断是不是记录了开始位置
               if (index == -1) {
                  index = i;
               }
               i++;
               j++;
               //判断是否已经找到了匹配串
               if (j == B.length) {
                  return index;
               }
           }else {           
               //套用公式：跳过长度=匹配到的字符串长度-PMT
               //k表示跳过的距离，其中j刚好代表了匹配了的字符串长度，getNext()返回了PMT
               int k = j - getNext(needle.substring(0, j));
               if (k == 0) {
                  k = 1;
               }
               i = s + k;//之前所谓把ptr移动位置，其实只是改变i就行
               s = i;//记录是从str中哪个位置开始匹配的
               j = 0;//从头开始匹配ptr
               index = -1;           
           }      
       }      
       //找不到匹配的
       return -1;     
    }
    public static int getNext(String str) {
       char[] B = str.toCharArray();
       int m= B.length;
       if (m<2) {
           return 0;
       }
       int[] F = new int[m];
       F[0] = -1;
       for (int i=1;i<m;i++)
       {
           int j=F[i-1];
           while ((B[j+1]!=B[i])&&(j>=0))
               j=F[j];
           if (B[j+1]==B[i])
               F[i]=j+1;
           else
               F[i]=-1;
       }
       return F[m-1]+1;
    }
}

啊想起面试的时候被问了这道题我懵逼了，因为虽然以前看过，但每次都是草草看了一遍就过，现在记录下来，应该会加深印象了嗯！