有几天未更新，全因为卡在了一个叫KMP算法的家伙，绕来绕去实在是让人头大，不过目前也算是搞懂了

题目选自LeetCode.28:找出字符串中第一个匹配项的下标：

这道题说白了就是在主串里面找到符合模式串的子串，用朴素模式算法也就是暴力破解，直接就可以秒杀，先来讲讲什么是朴素模式算法吧！

假设这里有一个主串S，模式串P，指针i指向S的第一个字符，j指向p的第一个字符

我们只需要判断S[i]是否等于P[j]即可，如果相等两个指针同时往后移动，如果直到P的所有字符都被比较完还是全部相等，那在S中，从[i-j到i-1]这一部分就是和模式串P所匹配的子串，

但是如果有不相等的字符，则要令i指向i-j＋1，也就是指向主串中被选出来进行匹配的子串的第一个字符的下一个字符，i也回到第一个字符，说白了就是一旦匹配不上，i就要回溯到第一个字符的下一个位置，重新进行匹配！

但是这个算法很明显非常不划算，比如上图这次匹配失败，i根本不用动，j指向P模式串的第二个字符就可以了，而用朴素方式的算法就得回溯很多次。

这个时候KMP算法的好处就体现出来了，在KMP算法中，i指针（指向主串的匹配指针）是不用回溯的，它一往无前！别看只是这一个特性，但是却可以将原本暴力破解O(n*m)的时间复杂度变成O(n+m)，

废话不多说，直接以这道题为例子开始讲KMP算法！

题目要求我们在haystack数组中找到与needle相匹配的子串的第一个匹配字符串，那我们只需要先找到相匹配子串，然后返回该子串的第一个字符的索引下标就可以了！

前面的步骤基本和朴素模式算法差不多！直接代码展示

注意：如果模式串的长度大于主串的长度，那肯定就无法在主串找到我们要的子串了！

所以我们在开头加一句判断，符合条件直接返回-1，也就是找不到我们要的子串!

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

需要解释的地方是：如果j等于0的话，这种情况就说明needle模式串与主串第一个字符就匹配失败了:

那这种情况我们就需要让j的第一个字符串和主串的下一个字符进行比较！所以我们令j等于-1.这样就满足了上面的判断条件，在下一次循环的时候，就会满足上面的判断条件，j从-1变成0，i则指向下一个字符，如下图所示:

嗯嗯这是第一个字符不相匹配的情况，那如果是大于0的情况呢？

很简单啊，只要让j等于对应next数组对应位置的值就可以了！next数组？你什么时候创建的？

其实就在开头，我创建了一个整形数组，并且这个数组由GetNext函数返回

此时，KMP算法的精髓来了，next数组的实现！

在讲怎么实现next数组前，我们先弄清楚什么是next数组，这个next数组的长度呢，他和我们模式串needle的长度是一样的，这么做的目的就是为了能对应needle数组每一个字符匹配失败时，我们应该做出的应对手段，没错，这个next数组就是为了找到needle对应位置匹配失败时，j指针应该指向的地方！

搞明白了next数组的What之后，现在我们来弄明白next数组的How实现:

首先我们先弄明白几个重要的概念：

---

前缀：必须包含第一个位置的元素，可以包含第一个位置（除了最后一个元素) 之后的元素的连续串.

后缀：必须包含最后一个位置的元素,可以包含最后一个位置（除了第一个元素)之前的元素的连续串.

最长相等前后缀：如果前缀和后缀的长度相等，并且元素都相同的话，就是相等的前后缀，最长就不用多说了吧！但是要注意的是后缀是从前往后看的，后缀和前缀并不是对称来看的

比如abba，ab和ba并不构成最长相等前后缀，最长相等前后缀应该是1，前缀和后缀都是a！

---

弄明白这些有什么用呢？

当然有用，比如当i位置的字符匹配失败时，我们就应该返回i-j+1到i-1处（红框）的最长相等前后缀!

根据我们前面所讲的概率，我们可以很容易地发现最长相等前后缀是1，为"i",

j指向1，也就是needle的第二个字符s，而i不变，

那现在我知道这个j指针是怎么动的了，可是我不明白j指针为什么要这样动啊！

其实原理也很简单，当有相等前后缀的时候，后缀连接着后面匹配失败的部分！我们设为p

前缀连接着前缀之外该子串的所有字符，我们就设前缀连接着的部分为x，

这部分x和p并不相等，但是连接着x和p的前后缀是相等的啊，那我们抵消掉相等的部分，让x代替p，重新和主串匹配失败的字符进行匹配不就可以啦！

若是没有最长相等前后缀那就没有可以相抵消的部分，只能从模式串的第一个字符开始匹配！

然后我们知道如果是第一个字符匹配失败的话，我们是不是会从让j=-1,随后i和j都++同时后移重新匹配，也就是说如果在有第一个字符串匹配成功之前我们是不会使用next数组的，因为next数组是依据最长前后缀实现的，如果只有一个字符，哪里来的前后缀一说呢？

有了这一点我们就可以知道跟needle匹配的子串，除了匹配失败的部分，前面部分其实都是和needle模式串相等的，既然如此，那我们实现next数组的时候，就没必要用到haystack主串了，只用needle一个模式串就可以了，

求出needle每一个位置的最长前后缀,

用j代表前缀的末尾，i代表后缀的末尾，当i等于0的时候，没有前后缀，默认为0，并且用for循环遍历i指针，除此之外，j还充当i当前位置的最长相等前后缀长度这一角色!因为只needle[i]==needle[j]的时候，j才会后移，j的值也才会＋1，

但是如果此时j不等于0了，并且needle[i]!=needle[j]，那该怎么办呢！我们知道此时前缀是"is"

后缀是"ip"，我们知道！i任何时候指向的位置就是后缀的末尾，后缀又必须包括末尾字符，所以我们不可能把i回溯，那就只能回溯j，找到新的首字符充当新前缀再匹配，那我们有必要从第一个位置0索引处开始找吗，也没必要，此时这里就相当于一个新的主串和模式串匹配，我们找到j前面的最长相等前后缀，而我们知道这段最长相等前后缀，和i指针所指向的位置的前面的最长相等前后缀是相等的，所以只要让j指向next[j-1]也就是抵消了最长相等前后缀之后的第一个字符就可以了！

但是上面的例子前一个字符的最长相等前后缀正好是0，并不能很好的解释这一现象！那你们自己想象一下就好了

但是博主会这么懒吗！不会！我重新举个例子给你们解释！

假设有这么一串模式串(省略前面n步)此时newNeedle[i]!=newNeelde[j]，

那我们就可以把前缀看成模式串，后缀看成主串:

这下看懂了吧，其实j=next[j-1]这一步，就是把前后缀的对比又看成了模式串和主串的对比!

具体代码如下:

public int[] GetNext(string s)
{
int j=0;
int[] next=new int[s.Length];
for(int i=1;i<s.Length;i++)//next[0]默认为0,从一开始
{
if(s[i]==s[j])
{
    j++;
}
else
{
    if(j>0)
    {
        j=next[j-1];
        if(s[i]==s[j])
        j++;
    }
}
next[i]=j;
}
return next;
}

最后返回到原函数，结束了while循环后，如果j等于模式串的长度，那就说明needle已经判断完毕，找到了所对应的子串,返回子串开头索引i-j，如果不相等返回-1，没找到对应子串

完整代码展示 ：

public class Solution {
    public int StrStr(string haystack, string needle) {
        if(needle.Length>haystack.Length)
        return -1;
        int[] next=GetNext(needle);
        int i=0;
        int j=0;
        while(i<haystack.Length&&j<needle.Length)
        {
            if(j==-1||haystack[i]==needle[j])
            {
                i++;
                j++;
            }
            else
            {
                if(j==0)
                {j=-1;}
                else
                j=next[j-1];
            }
        }
        if(j==needle.Length)
        return i-j;
        else
        return -1;
}
public int[] GetNext(string s)
{
int j=0;
int[] next=new int[s.Length];
for(int i=1;i<s.Length;i++)//next[0]默认为0,从一开始
{
if(s[i]==s[j])
{
    j++;
}
else
{
    if(j>0)
    {
        j=next[j-1];
        if(s[i]==s[j])
        j++;
    }
}
next[i]=j;
}
return next;
}
}