题目

the leetcode link

实现 strStr()
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言> > 的 strstr() 以及 Java 的 indexOf()) 定义相符。

示例 1：

输入：haystack = “hello”, needle = “ll”
输出：2

示例 2：

输入：haystack = “aaaaa”, needle = “bba”
输出：-1

示例 3：

输入：haystack = “”, needle = “”
输出：0

 

提示：

  • 0 &lt;= haystack.length, needle.length &lt;= 5 * 10<sup>4</sup>
  • haystack 和 needle 仅由小写英文字符组成

解题思路

首先，想想暴力解法的大致思路。
可以用两个指针分别在两字符串上游走，让p和s一个一个字符遍历匹配。
匹配过程中，s被看作分成四个区域：已放弃匹配，完成匹配，正在匹配，未匹配。tips: 正在匹配区域是1个字符。
p被看作分成两个区域：匹配，未匹配（包括正在匹配）。
如果发现字符匹配失败，就s要丢弃掉此次匹配情况，进入下一个匹配情况：
即完成匹配区域清0，已放弃匹配区域+1，正在匹配区域回退至已放弃匹配区域末端+1，剩下就是被增大的未匹配区域。
此时相应的，指针也都要回退： s回退到上次完成匹配区间的开始字符的下一个，p回退到开始，再遍历一个个匹配。

kmp其实是对回退过程的优化。
在发生匹配失败的时候，它能够通过观察p的当前匹配区域，看其前后两端是否具备镜像字符串。
记下最长的镜像字符串，p要回退到前边的最长镜像字符串末端+1，s不用回退
也就是说，要在p的匹配前缀的区域内，找最长相等前后缀，p上指针回退到最长相等前缀的末端+1，s不用回退；

Q:为什么找p匹配的两端镜像字符串（找最长相等前后缀）能够优化回退过程？
A： p匹配区的末端部分与s匹配区的末端部分原本确定是匹配吻合；
如果找到镜像字符串后，即p匹配区的前端镜像字符串部分=p匹配区的末端镜像字符串部分，也就可以确定p匹配区的前端镜像字符串部分与s匹配区末端部分也能匹配吻合。
tips：这里说s匹配区不包括正在匹配的字符，是指s匹配前缀。
那么在回退时，就可以巧妙地跳过这一已知吻合部分的比对匹配操作，直接从p匹配区的前端镜像字符串部分末尾+1与s当前匹配字符进行比对，节省时间。若比对匹配失败再回退。

Q: 回退过程如何找到跳跃落地点？
A: 这需要提前完成模式串p前缀表的初始化，我们会定义一个next数组，记下每一段的最长相等前后缀长度。
tips：其实该值真正的表示是：最长相等前缀末尾+1元素的下标。
匹配失败时，找p当前匹配区末端的对应的next元素值进行跳跃，则回退到正在匹配字符能够匹配成功的情况，没有就回到p的开始。

以上简单地理解了kmp的思想，至于如何实现，具体细节要回到代码当中。

代码

  1. 要初始化前缀表，记下每一段的最长相等前后缀长度，存入next数组，其实该长度值真正的表示是：最长相等前缀末尾+1元素的下标
    1.1 定义左右指针，右指针递增
    1.2 如果左右字符不相等，则回退到相等的情况，没有相等就回到p的开始
    1.3 相等则最长相等前后缀长度增加，左指针负责增加，右指针负责记录
  2. 文本串s和模式串p匹配
    2.1 定义两个指针i，j分别在两字符串中游走
    2.2 当匹配失败时，p通过next数组进行回退到匹配相等的情况
    2.3 否则，逐个匹配，增加匹配长度，一直到完全匹配成功
  3. 完全匹配不了，返回-1
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
class Solution {
    public int strStr(String haystack, String needle) {
        int len = needle.length();
        if(len == 0) return 0;
        char[] s = haystack.toCharArray();
        char[] p = needle.toCharArray();
        int[] next = new int[len];
        // next 初始化
        for(int left=0, right=1;right<len;right++){ //right go forward
            //left 回退
            while(left>0 && p[left] != p[right]){
                left= next[left-1];
            }
            //匹配长度增加
            if(p[left] == p[right]){
                left++;
            }
            next[right] = left;
        }

        for(int i=0,j=0;i<s.length;i++){ //s go forward
            //p回退
            while(j>0 && s[i] != p[j]){
                j= next[j-1];
            }
            //匹配长度增加
            if(s[i] == p[j]){
                j++;   
            }
            //完全匹配
            if(j == len) return i-len+1;
        }
        return -1;

    }
}