[Leetcode] 28. Implement strStr()

[Leetcode] 28. Implement strStr()

这道题在leetcode里面是easy，显然，leetcode是没希望我们用KMP来解题的。但是KMP是最优策略。我们就用KMP来尝试解题，也借用此题，来彻底弄懂KMP。这篇

从头到尾彻底理解KMP 文章 介绍KMP炒鸡详细而且深入浅出。这个视频讲的也很好当然，这个题要是能用API的话，String.indexOf()秒搞定。。。这篇文章也很好KMP算法详解

题目大意：

在一串字符串中，找到匹配串。

解题思路：

1. 最简单的暴力破解。一个一个对比，匹配上，上（i）下(j)全移动到下一个，匹配不上，j返回起点0，i = i-j+1. i 向后挪一格。复杂度O(mn)的我的暴力代码：

public class Solution {
    public int strStr(String haystack, String needle) {
        int l1 = haystack.length();
        int l2 = needle.length();
        int result = -1;
        if(l2==0){
            return 0;
        }
        if(l1 == 0){
            return result;
        }
        int i=0;
        int j=0;
        while(i<l1 && j<l2){
            if(haystack.charAt(i) == needle.charAt(j) ){
                i++;
                j++;
            }
            else{
                i = i-j+1;
                j = 0;
            }
        }
        if(j == l2){
            result = i-j;
        }
        
        return result;
    }
}

2. KMP 这个方法最nb的地方在于，比较过的如果有相同的就不再比较了。我们把上面的字符串叫做文本串S，下面的叫匹配串P。这个方法，我给起了个名字，叫前缀后缀匹配。
下面是引用的上面链接中的讲解。

举个例子，如果给定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，现在要拿模式串P去跟文本串S匹配。比较到如下的时候，S中的空格和P中的D不匹配了。
BBC ABCDAB ABCDABCDABDE
        ABCDABD
要是按照方法1， 我们就i向后一格，j到0。
BBC ABCDAB ABCDABCDABDE
           ABCDABD
但是我们知道，P中的前缀AB和S中的后缀AB，是一样的，所以，这个可以不用在比，而是直接比较P里面AB后面的，和S里面AB后面的。
这时，我们引入一格next[]数组，专门记录这个前后缀信息。这个机理是，如果P串的后缀等于P串的前缀，由于在失配之前，P和S都是匹配的，也就是说，S中相应位置的后缀等于P失配前的后缀 =》由此推出，P的前缀等于S失配前的后缀。所以，我们可以保持i不变，将P的j指针，直接跳过前后缀匹配的地方next[j]，避免不必要的重复计算。上文的链接里有更详细的解读。

计算next数组，就变成了我们下一步要做的最重要的事情了。
这段还是引用上面文章的，文章作者理解的太好了，都不知道该咋改

• 1. 如果对于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于next[j] = k。
• 此意味着什么呢？究其本质，next[j] = k 代表p[j] 之前的模式串子串中，有长度为k 的相同前缀和后缀。有了这个next 数组，在KMP匹配中，当模式串中j 处的字符失配时，下一步用next[j]处的字符继续跟文本串匹配，相当于模式串向右移动j - next[j] 位。

举个例子，如下图，根据模式串“ABCDABD”的next 数组可知失配位置的字符D对应的next 值为2，代表字符D前有长度为2的相同前缀和后缀（这个相同的前缀后缀即为“AB”），失配后，模式串需要向右移动j - next [j] = 6 - 2 =4位。

BBC ABCDAB ABCDABCDABDE
        ABCDABD

BBC ABCDAB ABCDABCDABDE
                  ABCDABD

• 2. 下面的问题是：已知next [0, ..., j]，如何求出next [j + 1]呢？

    对于P的前j+1个序列字符：

• 若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1；
• 若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]，则next[ j + 1 ] =  next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀"p0 p1, …, pk-1 pk"跟后缀“pj-k pj-k+1, …, pj-1 pj"相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么这个t+1 便是next[ j+1]的值，此相当于利用已经求得的next 数组（next [0, ..., k, ..., j]）进行P串前缀跟P串后缀的匹配。

以上是所有的核心步骤，again，上面文章里有更详尽的解释。理解到这，程序思路也就基本成型了。next数组的第二部是全篇最难的部分。要记住的是，求next数组跟两个字符串比较之间是分开的，这是两个过程，next数组只和P，也就是匹配串有关系 。逻辑上一定要清楚。


我理解中的难点是，next数组是怎么求的这步。知道next数组好用，但是我一开始想的求next数组的方法还是n方的复杂度。不过作者这里就很巧妙了，如果当前p[j]和已经有的前缀的下一个字符p[k]相等，next [j] + 1 = k + 1。要是不相等，那这条线肯定是连不起来了，但是我们可以找比这个k短的还有没有。有的话，next[ j+1]就是这个短的的值。

AC答案：

//这个答案是我自己写的 :)

public class Solution {
    public int strStr(String haystack, String needle) {
        int result = -1;
        int ln = needle.length();
        int lh = haystack.length();
        if(ln == 0){
            return 0;
        }
        if(lh == 0){
            return result;
        }
        int i=0;
        int j=0;
        int[] next = getNext(needle);
while(i < lh && j < ln){
  if(j == -1 || haystack.charAt(i) == needle.charAt(j)){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        if(j == ln){
            result = i-j;
        }
        return result;
    }
    
    private int[] getNext(String needle){
        int k=-1;
        int j=0;
        int l = needle.length();
        int[] next = new int[l];
        next[0] = -1;
        while(j < l-1){
            if(k == -1 || needle.charAt(j) == needle.charAt(k)){
                j++;
                k++;
                next[j] = k;
            }
            else{
                k = next[k];
            }
        }
        return next;
        
    }
}

上面链接的文章作者写的太好，我这个是方便自己记忆的超简化版，看不懂的就甭看了，直接链接到原文。以后要是有写的好的，我就不写思路，只写简化版，把好的链接贴上来。Fighting！