硬怼KMP算法——LeetCode每日一题：实现 strStr()

在介绍KPM算法之前，还是先介绍基本的暴力解法吧，暴力解法思路还是比较简单的，就是把目标字符串的第一个字符逐一与haystack给定字符串的字符相比较，如果相同则开始比对后续字符是否也相同，如果都相同则返回位置，不相同则回溯，继续比对接下来的字符，这里也不多说了

代码：

 class Solution {
public int strStr(String haystack, String needle) {
    int len1 = haystack.length();
    int len2 = needle.length();
    if(len2 == 0){
        return 0;
    }
    if(len2 > len1){
        return -1;
    }
    int l1 = 0;
    int l2 = 0;
    int res = -1;
    boolean flag = false;
    while(l1 < len1){
        if(haystack.charAt(l1) == needle.charAt(l2)){
           res = l1;
           int index = l1;             
            if(len1 - index < len2){
                   return -1;
            }
           while(l2 < len2){                
               if(haystack.charAt(index) == needle.charAt(l2)){
                   l2++;
                   index++;
               }else{
                   flag = true;
                   l2 = 0;
                   break;
               }
           }
           if(flag){
               flag = false;  
               res = -1;        
           }else{
               return res;
           }
        }
        l1++;
    }
    return res;
}
}

优化版本代码，直接比较字符串：

 class Solution {
public int strStr(String haystack, String needle) {
    int len1 = haystack.length();
    int len2 = needle.length();
    if(len2 == 0){
        return 0;
    }
    if(len2 > len1){
        return -1;
    }
    int l1 = 0;           
    while(l1 + len2 <= len1){
       if(haystack.substring(l1,l1+len2).equals(needle)){
           return l1;
       }else{
           l1++;
       }
    }
    return -1;
}
}

方法二：KMP算法

KMP算法（Knuth-Morris-Pratt算法）是一个著名的字符串匹配算法，效率很高，但是十分难以理解，我也是在看了好多篇博客的情况下，才能大体知道其思路，可见其算法之精妙。

首先介绍一下kmp算法的核心，部分匹配表是怎样产生的：

要了部分匹配表的产生首先要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

以这个部分匹配表为例，搜索词的部分匹配值实际上就是这个字符串的最长公共前后缀的长度：

－　"A"的前缀和后缀都为空集，共有元素的长度为0；

－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为 0；

－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0

这样就创建了一个部分匹配表，代码实现：

public static int[] kmpNext(String str) {
  int[] next = new int[str.length()];
  next[0] = 0;  //第一个部分匹配值为0
  for(int i = 1,j = 0;i < str.length();i++) {
      while(j > 0 && str.charAt(i) != str.charAt(j)) { 
          j = next[j-1];
      }    
      if(str.charAt(i) == str.charAt(j)) {
          j++;  //部分匹配值加一
      }
      next[i] = j;
   }
   return next;
}

部分匹配表生成完毕后，就可以开始kmp算法的实现了：

以这个例子为例：

首先还是开始逐一比对字符，看是否相等，直到出现不相等的情况，图中箭头所指处为不相等的地方：

然后把箭头所指的前面的字符串（方框框起来的）作为一个整体，求这部分的部分匹配值，其公共前后缀为AB，那么它的部分匹配值即为AB的长度即为2

然后就可以直接把其向后移动目标数组当前下标（箭头所指的地方）- 部分匹配值 = 3位，直接从部分匹配值+1（箭头所指处）的地方开始比较

上面方框框起来的部分就相当于已经匹配完成了，直接从后面开始匹配即可

接下来继续比较看字符是否匹配，到箭头所指处又不匹配，则重复上面的步骤寻找部分匹配值

可以看出其公共前后缀为A，则后移目标数组当前下标（箭头所指的地方）- 部分匹配值 = 6 - 1 = 5位，

继续比对，发现未找到目标值，结束循环，代码实现：

 public int strStr(String haystack, String needle) {
    int len1 = haystack.length();
    int len2 = needle.length();
    if(len2 == 0){
        return 0;
    }
    if(len2 > len1){
        return -1;
    }
    int[] next = kmpNext(needle);
    int index = 0;
    for(int i = 0;i < len1;i++){
          int temp = i + index;
          while(index < len2){
              if(len2 > len1 - i){
                 return -1;
              }
              if(haystack.charAt(temp) == needle.charAt(index)){
                  temp++;
                  index++;
              }else{
                  if(index != 0){   
                  //加上目标数组当前下标 - 部分匹配值  
                  i = i + index - next[index - 1] - 1;    
                  index = next[index - 1];
                  }
                  break;
              }
              if(index == len2){
                  return i;
              }
          }
    }
   
  return -1;
}

总结："部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，字符串"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。
本人也还在学习阶段，如有错误，欢迎指正！