KMP算法，可读性较好的一种实现。

最近看了July的博文《从头到尾彻底理解KMP》。讲解得非常详细，也给我一些启发，让我仔细地思考了一下KMP算法。

作为产品维护工程师，我们会更多地考虑代码的可维护性，即代码的可读性。July的文章中，在计算next数组时，给next数组的第0位设置为－1做为旗标使用，并且在字符失配的情况下，令k＝next[K]，这样的写法让人比较难以理解。于是我也写了一份计算next数组的实现，供大家参考。

 1     public static int[] getNextArray(String p)
 2     {
 3         int len = p.length();
 4         int next[] = new int[len];
 5         next[0] = -1;
 6         if (len >= 2)
 7         {
 8             next[1] = 0;
 9             int cursor = 2;
10             int flag = 0;
11             int value = 0;
12 
13             while (cursor <= len -1)
14             {
15                 if (p.charAt(cursor - 1) == p.charAt(flag))
16                 {
17                     ++flag;
18                     ++value;
19                 }
20                 else
21                 {
22                     if (flag != 0)
23                     {
24                         flag = 0;
25                         value = 0;
26 
27                         if (p.charAt(cursor - 1) == p.charAt(flag))
28                         {
29                             ++flag;
30                             ++value;
31                         }
32                     }
33                 }
34                 next[cursor] = value;
35                 ++cursor;
36             }
37         }
38 
39 
40         return next;
41     }

next数组的含义是：设i是next数组中的一位，则next[i]的值的含义是在这一位之前自负串中相同的前缀和后缀的长度。比如字符串ABCABD，当i＝5，即字符D位置，该位置之前的字符串为ABCAB，有相同的前后缀AB，其长度为2，则对应next数组的值为2。需要指出的是，位置0和1比较特殊。位置0之前没有字符串，对应next数组的值设置为－1，这个值是做为占位符存在的，其值除了做为旗标外并无其他意义。而位置1之前，只有一个字符，此处认为其前后缀为0。

我的实现和之前博文描述的不同之处在于适配时候的处理。在计算next数组时，当适配发生的时候，如果当前字符不是和字符串的第一位进行比较，需要再和字符串第一位进行一次比较。在此实现中，我用flag代表前缀的游标，value做为当前next数组的值，可以看到，这两个变量的增减变化是同步的。其实是可以合在一起的。然而，合在一起的代价就是对程序理解的变得更困难了，因为flag和value在含义上并没有必要的联系。这也是之前next[k]=k在理解上面的难点。

next数组完成之后，KMP算法的实现也就变得唾手可得了。附上我自己的实现供大家参考。

 1     public static int kmpMatch(String s, String p)
 2     {
 3         int ret = -1;
 4         int i = 0;
 5         int j = 0;
 6 
 7         int[] next = getNextArray(p);
 8         while ( i < s.length() - p.length()+1)
 9         {
10             if (s.charAt(i) == p.charAt(j))
11             {
12                 if (j == p.length() -1)
13                 {
14                     ret = i - j;
15                     break;
16                 }
17                 else
18                 {
19                     ++i;
20                     ++j;
21                 }
22             }
23             else
24             {
25                 if (j != 0)
26                 {
27                     j = next[j];
28                 }
29                 else
30                 {
31                     ++i;
32                 }
33             }
34 
35         }
36 
37         return ret;
38     }