KMP算法

经过一下午的倒腾，终于把KMP算法搞明白了一点。

只能怪我脑筋过来好吧。。其实并没有那么难，想明白了也就那么回事，当然是看着大神细致的讲解才明白的。。

这里给出大佬的博文：https://www.cnblogs.com/yjiyjige/p/3263858.html

讲的很详细

这里说一下我自己的理解吧。

简单而言就是关键字匹配

字符串匹配吗，这有什么难的，java都给我们封装了实现，但了解算法原理也是很有必要的，可以锻炼自己的思维

首先，我们很直观的想法就是“暴力破解”，

这里给出我的实现

 1 package com.java.demo.算法.kmp;
 2 
 3 public class t1 {
 4     public static void main(String[] args) {
 5         String p = "abcdef";
 6         String q = "c";
 7         System.out.println(count(p, q));
 8     }
 9 
10     static int count(String p,String q){
11         char[] ps = p.toCharArray();
12         char[] qs = q.toCharArray();
13         int i=0;
14         while (i+qs.length != ps.length-1){
15             int cnt = 0;
16             for (int j=0;j<qs.length;j++,i++){
17                 if (ps[i] == qs[j]){
18                     cnt++;
19                 }
20             }
21             if (cnt == qs.length){
22                 return i-qs.length;
23             }
24 
25             i = i-qs.length+1;
26         }
27         return -1;
28     }
29 
30 
31 }

View Code

这种想法比较直观，也很好理解。无非就是就是逐个验证，从脑袋开始匹配，不匹配则从开始处进一，模式串归0，继续匹配。

当然，对于大神来说，自然不屑这种低效的方法。

D.E.Knuth、J.H.Morris和V.R.Pratt这三个大哥就一起发现了KMP算法。

我们用画图的方式，便于理解

如图，如果是暴力的方法，就是匹配A开始，到C发现不匹配了，那么我就从上面的B开始重新匹配，这种方式效率很低下

但如果是KMP算法，它就比较智能了。

它发现C前面也有A啊，跟开头一样，它就选择把开头B挪到它现在的位置

这样下面的A和上面的A就对上了。

我也不知道自己在说什么，sorry。。毕竟只是小白，建议大家去看大佬的博文，讲的很详细。

但我选择继续扯下去。。

简而言之，就是有一个匹配串，你拿过来看，那两个字母是重复的，那么你就把它们后面的字母下标做个对应关系，就是如果你后面位置的字母发现不匹配了，

它就去找它前面一个小伙伴，为啥咧，因为它们各自前面一个字母是相同的吗，映射到现实中，就是两个人姓相同，五百年前是一家。

如果还找不到呢，那就再找他前一个小伙伴，一直找到第一个小伙伴，发现前面没人了，那么被匹配串，老家伙你往后面挪一位吧。

 1 static int[] getNext(String p){
 2         char[] ps = p.toCharArray();
 3         int next[] = new int[p.length()];
 4         next[0] = -1;
 5         int j=0;
 6         int k=-1;
 7         while (j < ps.length-1){
 8             if (k == -1 || ps[k] == ps[j]){
 9                 //这是优化后的操作，因为如果j位置的不匹配的话，那么与之相等的k位置的也一定不匹配
10                 if (ps[++j] == ps[++k]){
11                     next[j] = next[k];
12                 }else{
13                     next[j] = k;
14                 }
15 //                next[++j] = ++k;
16             }else{
17                 k = next[k];
18             }
19         }
20         return next;
21     }

我们来分析一下这个方法，这是算法的关键

这里主要解释一下k=next(k)，

前面的应该比较好理解，if中增加了一个if判断，因为如果j和k对应的字母相同，如果j不匹配，那么k也没有比较的必要了，继续找前面一个小伙伴吧。

这里的k=next[k]的意思，可以用一句话来说明，就是退而求其次

它发现k和j对应的值不相等了，不慌，我们继续找k的字串中有没有找到和j对应的字母相同的。

道理就这么个道理。我以前还想过当讲师，现在想想，算了吧。。就别误人子弟了

差点忘了，

把剩下的代码贴出来

 1 static int KMP(String p,String q){
 2         char[] ps = p.toCharArray();
 3         char[] qs = q.toCharArray();
 4         int i=0,j=0;
 5         int[] next = getNext(q);
 6         while (i<ps.length-qs.length && j<qs.length){
 7             if (j == -1 || ps[i] == qs[j]){
 8                 i++;
 9                 j++;
10             }else{
11                 j = next[j];
12             }
13         }
14         if (j == qs.length){
15             return i-j;
16         }
17         return -1;
18     }