题目

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

要找出符合的字符串，最暴力的方法是通过两个for循环来解决。

首先我们设置needle[0] 与haystack[0] 左边对齐比较，如果相同就比较 needle[1] 与haystack[1]，如果不相同则让needle右移一位，使needle[0] 与haystack[1] 对齐比较。如图所示以此类推，直至找到结果。

这么做的结果是每次needle比较失败，都会往后移动一格，然后重新从头开始比较。最差的结果就是每次比对到最后一个才发现不对，这样就要从第一位开始比对起，所以最坏的打算就需要O(m*n)。

为了优化这个方法，我们可以采用KMP(The Knuth-Morris-Pratt Algorithm)算法，这样我们可以更快一点解决问题，优化算法为O(m+n)。

接下来用尽量简洁的篇幅让你明白这个伟大的算法。

算法逻辑：

首先声明所有数组第一个下标从0开始。(有些教程会选择从1开始，先说清楚，以免搞混了)。

这里我们使用一个例子来简单说明一下

例如

如果我们用暴力寻找的话，那么过程是：

总共比对了 4 + 1 + 1 + 1 + 7 + 1 +1 + 1 + 3 + 1 + 1 + 8 +1 +1 +1 +8 = 41 (次)

如果改进成KMP的话，那么运算过程就是(灰色地方是KMP算法不去考虑的地方，红点是每次比较的字符串位置)

image.png

总共比对了 4 + 1 + 7 + 1 + 1 +8 + 4 = 26 (次)

如果我们看红点在abcxabcdabxabcdabcdabcy的位置，我们就会发现红点一直在向前移动，不会往后退/回头。这就是KMP算法的优点即不会倒退(也有人称作回溯)，所以就能避免不必要的匹配检查。

让我们依次看看KMP算法在上面的例子中都做了些什么。

首先让我们看一下第一个例子。

image.png

绿框中是KMP算法跳过的地方，那么我们就来对比一下两个红框里面的内容。

image.png

这里我们可以看到，深绿色方框那里是不相同字符的位置与新一轮判定的开始位置。

深橘黄色方框里的是已经匹配成功的字符串 abc。

关键的地方来了，因为已经匹配成功的字符串abc中没有相同的前后缀，所以下一次比对要从abcdabcy的首位开始比较。

我们简单地来看一下abc的前后缀情况。

要注意，这里我们看的前后缀的长度要小于已匹配到的字符串长度，因为如果长度一样了那就不用分前后缀了，也没有比较的意义了。

因为没有相同的前后缀，我们就不用担心错过什么，直接从配对失败的地方开始新的匹配就行了。

这个很好理解，让我们假设一下如果在上面这个例子中间有这么一种情况

在这里如果符匹配条件我们至少需要满足方框内的字符相同。

让我们看看方块内的字符处于abc中的什么位置

在黄色框内，bc属于abc的后缀，ab属于abc的前缀，所以如果条件符合的话，abc需要有相同的前后缀。

不理解为什么的同学不用担心，现在只要记住我们在寻找相同前后缀就行了，一会看完应该就能想通了。

让我们看看下一个例子。

在这个例子中KMP算法跳过了绿色方框的部分，直接运行了红色方框里的内容。让我们看看红色方框里发生了什么

深绿色方框位置是不相同字符位置与新一轮比较的位置。

深橘黄色方框里的是已经匹配的字符串 abcdab。

让我们来找一下 abcdab的前后缀吧。

我们发现abcdab有相同的前后缀。

重点又来了，如果有相同的前后缀，我们就需要把前缀移动到后缀的位置上。

这样abcdabcy就向右移动了四位，然后开始比较abcdabcy[相同前后缀长度] 上的字符，即第3个字符c(默认索引从0开始)。

不明白没有关系，我们再看两个例子。

在上面这个例子中，绿色依然是被忽略的部分，红色方框是KMP算法执行的部分。

让我们继续关注红色方框里的内容：

深绿色的地方是匹配到不一样字符的位置，也是下一次比较的开始位置。

深橘色的地方是已经成功匹配的字符串ab。

由于ab没有相同的前后缀，所以下一次比较从abcdabcy开始。

最后我们看看这个例子

依旧只看红色方框部分

深绿色的地方是匹配到不一样字符的位置，也是下一次比较的开始位置。

深橘色的地方是已经成功匹配的字符串abcdabc。

让我们来看看abcdabc的前后缀吧。

我们发现abcdabc有相同的前后缀abc，我们就需要把前缀移动到后缀的位置上。

这样abcdabcy就向右移动了四位，然后开始比较abcdabcy[相同前后缀长度] 上的字符，即第3个字符d(默认索引从0开始)。

最后我们比对发现找到了目标字符串。

通过上面的例子，我们发现每当我们匹配失败，就需要寻找匹配成功的字符串中有没有相同的前后缀（最长的前后缀），然后再判定下一次比较要从哪一位开始。
逻辑实现：
还是回到上面的例子，如果每次匹配失败都去判定一次是否有相同前后缀的话，那么就太麻烦了，所以我们可以在匹配前就把各种情况的前后缀找出来。

上面是我们能列举出来的所有情况，KMP算法需要的关键信息就是最左边的匹配数与最右边的前/后缀长度。

因为8匹配就匹配完成，所以我们其实只需要考虑0～7匹配的情况，总共8种情况。

我们可以用一组数组来保存此数据，我们命名此数组为next数组。

int[] next = new int[] { 0,0,0,0,0,1,2,3};

所以每当我们匹配失败的时候，我们就可以通过next数组来快速定位下一个需要对比的索引位置。

这样我们的KMP算法可以理解为

KMP(string target, string txt){
    1）计算next数组
    2）通过循环来对比target与txt字符串
}

代码实现：

1. next数组

这里推荐一下个人觉得不错的视频，如果感兴趣的话可以深入了解一下https://www.bilibili.com/video/BV1Ys411d7yh?05:33，在5分33秒的时候开始讲解next数组的逻辑。（Ps：相信我，一遍可能看不懂，看三遍肯定会看懂了！！！）
整体的逻辑流程如图所示：

代码如下：

private int[] GetNext(string str){ 
    int[] next = new int[str.Length];
    next[0] = 0;
    int i = 1;
    int j = 0;
    while(i < str.Length)
    {
        if (str[i] == str[j])
        {
            j++;
            next[i] = j;
            i++;
        }
        else
        {
            if (j == 0)
            {
                next[i] = 0;
                i++;
            }
            else
            {
                j = next[j - 1];
            }
        }
    }
    return next;
}

2. KMP 算法的比较逻辑

然后我们再来梳理一下KMP算法取得next数组之后的逻辑。
很多人喜欢写做i，j。其实就是haystack与needle的下标，用hi 与 ni 来表示的话个人感觉会清晰一点。

代码可以写作：

private int KMP(string haystack, string needle)
{
    int[] next = GetNext(needle);
    int hi = 0;
    int ni = 0;
     
    while (hi < haystack.Length) { 
        if (haystack[hi] == needle[ni]) { 
            ni++; 
            hi++; 
        }
         
        if (ni == needle.Length)
        {
            return hi - ni;
        }
        else if (hi < haystack.Length && haystack[hi] != needle[ni])
        {
            if (ni != 0)
                ni = next[ni - 1];
            else
                hi++;
        }
    }
    return -1;
}

接下来我们就可以写出KMP的主方法了。

private int KMP(string haystack, string needle)
{
    int[] next = GetNext(needle);
    int i = 0;
    int j = 0;
    while (i < haystack.Length) { 
        if (haystack[i] == needle[j]) { 
            j++; 
            i++; 
        }
        if (j == needle.Length)
        {
            return i - j;
        }
        else if (i < haystack.Length && haystack[i] != needle[j])
        {
            if (j != 0)
                j = next[j - 1];
            else
                i++;
        }
           
    }
    return -1;
}

在运行KMP之前对输入参数进行一些简单的校验：

if (string.IsNullOrEmpty(needle))
{
    return 0;
}
        
if (needle.Length > haystack.Length || string.IsNullOrEmpty(haystack))
{
    return -1;
}

所以全部代码为：

public class Solution {
    public int StrStr(string haystack, string needle)
    {

        if (string.IsNullOrEmpty(needle))
        {
            return 0;
        }

        if (needle.Length > haystack.Length || string.IsNullOrEmpty(haystack))
        {
            return -1;
        }

        return KMP(haystack,needle);
    }
}

private int KMP(string haystack, string needle)
{
    int[] next = GetNext(needle);
    int i = 0;
    int j = 0;
    while (i < haystack.Length) { 
        if (haystack[i] == needle[j]) { 
            j++; 
            i++; 
        }
        if (j == needle.Length)
        {
            return i - j;
        }
        else if (i < haystack.Length && haystack[i] != needle[j])
        {
            if (j != 0)
                j = next[j - 1];
            else
                i++;
        }
           
    }
    return -1;
}

private int[] GetNext(string str){ 
    int[] next = new int[str.Length];
    next[0] = 0;
    int i = 1;
    int j = 0;
    while(i < str.Length)
    {
        if (str[i] == str[j])
        {
            j++;
            next[i] = j;
            i++;
        }
        else
        {
            if (j == 0)
            {
                next[i] = 0;
                i++;
            }
            else
            {
                j = next[j - 1];
            }
        }
    }
    return next;
}

结语

感谢牛客大佬bailixi的讲解，本文主要是大佬在leetcode上的讲解并对其中错误地方进行了更正。如果在文中还有说错的地方或有疑惑的地方请留言告诉我，我看到了会尽快回复！希望帮助大家一起理解KMP算法，觉得不错的话也请点个赞，谢谢！！！！
这里附上大佬的讲解链接：
https://leetcode-cn.com/problems/implement-strstr/solution/c-kmp-xi-wang-wo-jiang-ming-bai-liao-kmpsuan-fa-by/