代码随想录9——字符串：KMP算法求解28.实现strStr()

参考： 代码随想录28.实现strStr()，其中也有B站视频，可以好好去看一下。

1.KMP算法原理

1.1.前缀表

1.1.1.前后缀

这里先给出KMP算法中需要使用到的前缀表的定义，后面分析KMP算法的时候自然会明白为什么要定义这样的一个前缀表，然后会详细解释如何获得这个前缀表。

首先定义一个字符串的前后缀，以字符串abcd为例：

• 前缀：不包括尾字符的前面所有字符，也就是abc；
• 后缀：不包括首字符的后面所有字符，也就是bcd。

注意：注意严格按照上面的定义来区分前后缀即可，比如字符串aaa，那么它的前缀就是前两个aa，后缀就是后两个aa。

1.1.2.最长相等前后缀

知道了前后缀，那么就可以定义一个字符串的最长相等前后缀，比如一个字符串abcDabc，它的最长相等前后缀就是abc，即长度为3。

1.1.3.前缀表

这个前缀表和上面说的字符串的前缀不是一个意思，可以认为他就是描述一个字符串前后缀关系的一个表，只不过叫做前缀表，你也可以叫它xx表等，所以不要和字符串的前缀弄混了。前缀表在代码中通常称为next数组。

上面已经说了最长相等前后缀，那么给定一个字符串aBaDaBa，他一共有7个字符，截止到每个字符的位置（包括这个字符）的子字符串的最长相等前后缀，就作为这个位置上的前缀表的值。下面直接用next数组表示这个前缀表不同位置的值：
（1）next[0]，此时子串是a，显然前后缀都没有字符，所以最长相等前后缀是0，所以next[0]=0；
（2）next[1]，此时子串是aB，显然前缀字符是a，后缀字符是B，不相等，所以next[1]=0；
（3）next[2]，此时子串是aBa，最长相等前后缀字符串是a，next[2] = 1；
（4）（5）（6）
（7）next[6]，子串是aBaDaBa，最长相等前后缀字符串是aBa，所以next[6] = 3。

1.2.KMP算法查找子串

使用KMP算法查找子串的思想就是，利用最长相等后缀作为桥梁，复用已经匹配的部分字符串，从而提高效率。

如下图所示，在abDabDabF中查找abDabF：

一开始我们从头对比，一直对比到红色箭头的地方发现匹配不上了。如果使用双重循环的暴力方法，那么此时就是把下面的目标串向后移动一个位置，也就是从源串的第二个位置再依次向后对比。这样显然比较耗时，如果源串是n个字符，目标串是m个字符，那么双重for循环，时间复杂度就是O(n*m)。

而KMP算法的核心思想，就是利用事先计算的目标串的前缀表next数组来重复利用已经匹配的子串。比如上面这种情况，KMP算法的思想就是三个步骤：

• 箭头2：在F的位置发现不匹配了，目标串从F之前的子串（不包括F，也就是abDab）的最长相等前后缀我们是事先计算好的，也就是ab两个字符，即图中的箭头2，后缀和前缀是相等的。
• 箭头1：同时我们直到在F的位置出现了不匹配的情况，那么说明在F之前的目标串的子串是能和源串匹配上的，那么自然其中的ab两个子串也是能够匹配上的，即图中的箭头1，源串中的ab可以和目标串中的后缀ab匹配上。
• 箭头3：融合箭头1和2，我们就可以把目标串的前缀ab和源串的ab匹配上，这样就相当于我们直接把目标串移动到了源串的绿色框住的ab的位置，然后继续向后匹配，也就是从蓝色箭头的位置继续向后匹配。这样就比一次移动一步进行匹配高效的多。

上述就是KMP算法的核心思想，就是利用后缀作为桥梁，再移动目标串的时候，直接把前缀移动到本次源串和后缀匹配的位置，然后继续匹配，从而提高了效率。

2.目标串的前缀表计算

代码实现的时候，有两个索引i和j：

• i指向后缀字符串的末尾
• j指向前缀字符串的末尾，同时j也是最长相等前后缀的长度

2.1.初始化前缀表

j = 0;
next[0] = 0;

这个很好理解，前缀字符串一开始就在第一个位置，然后第一个位置的最长相等前后缀长度是0

2.2.向后遍历i寻找每个位置的最长相等前后缀

i显然从1开始，因为只有这样才能比较前后缀。

2.2.1.前后缀相等的情况

比如字符串aabaaf，计算它的前缀表。

• i = 1：此时前缀末尾s[j]和后缀末尾s[i]相等，那么先把j++，然后next[i] = j。首先前面说了，j表示的不仅是前缀的末尾，也是最长相等前后缀的长度，所以j++之后，它指向了一个新的前缀字符串末尾，同时也表示它是这次计算的最长相等前后缀的长度，所以把j赋值给next数组的[i]的位置。
  

• i = 4：这个时候更加能够看出来为什么j++之后，j就可以代表最长前后缀的长度。其实这也是一种复用，就是说遍历到此时的j/i的位置的时候，j = 1，已经说明在当前前后缀的子串中，前面有一个子串是相等的了，也就是图中框出来的两个绿色的位置，这是上次计算前缀表的时候得到的。因此这次我们只需要再判断此时j/i位置的字符是否相等，如果相等，那么最长相等前后缀的长度又可以加一。

2.2.2.前后缀不相等的情况

如图所示，假设前面的已经计算好了，我们以目前i遍历到最后这个字符为例，去理解代码随想录中求前缀表时前后缀不相等的回退的原理。

此时j=7，和上面前后缀相等的解释一样，也就是上一次i的位置，在i之前包括i的字符串的最长相等前后缀的长度。但是现在j/i的位置指向的元素不相等，那么肯定j就要向前走，去找一个更短的前缀和当前的后缀进行匹配。那么j向前走，走到哪里呢？这里就和KMP算法一样，走到next[j-1]所指向的位置，这里next[j-1]=3，所以j走到字符D的位置，即图中第一步红箭头所示。

关键是，为什么这么做？

假设最后一个字符是D（最后一个字母是b的话是另外一个举例，看下面的分析）：其实这里和KMP算法的思想是一样的，此时就相当于我们在用j之前（包括j）的字符串（目标串，也就是abaDabaF），去匹配j之后（不包括j，也就是abaDabaD）的字符串（源串），但是发现j的位置和i的位置匹配不上，如下图所示，在红色箭头的位置匹配不上了。那么按照KMP算法的思想，我就重复利用j之前（不包括j）的子字符串的最长相等前后缀，以后缀作为桥梁，目标串的前缀（目标串中的前面的绿框，即aba）直接就和 源串中与目标串的后缀对应的位置（源串中的绿框，即aba）匹配上了，所以只需要从目标串的前缀（目标串中的前面的绿框，即aba）后面的位置（即蓝色箭头位置，字符D）开始匹配就行了。匹配过程如下图，和前面说的KMP算法是一样的。此时从蓝色箭头开始匹配，发现恰好可以匹配上，那么最长相等前后缀的值就是4，最长相等前后缀的字符串就是abaD。

注意：这里使用KMP算法的思想是一样的，但是和原来从源串中查找目标串并不完全一样。因为我们这里其实并没有明确的目标串，而是一直在缩小目标串的长度（也就是最长相等前后缀字符串），直到可以和源串的最后几个字符匹配上。比如说如果最后的字符是b：

接上面的操作，如果最后的字符是b，可见蓝色箭头的位置并不匹配。其实这个时候问题就变成了abaD和abab匹配的问题，如下图：

还是用KMP的算法，既然D的位置不匹配，那么就看他前面的子串（不包括D），利用前面子串的最长后缀作为桥梁，再次往后匹配，如上图的右边所示，可见b的位置匹配上了，那么说明最后最长相等前后缀的长度就是2，最长相等前后缀的字符就是ab。

2.3.代码

  void getNext(int* next, const string& s)
    {
        // 1.初始化
        int j = 0;     // 前缀字符串末尾
        next[0] = 0;   // 第一个位置的最长相等前后缀一定是0

        // 遍历这个字符串，求前缀表
        for(int i = 1; i < s.size(); i++)
        {
            // 2.前后缀字符不相等，使用KMP的思想回退前缀字符的尾指针，直到和后缀字符匹配上
            while(j > 0 && s[j] != s[i])
                j--;
            
            // 3.前后缀字符相等，则前缀指针后移，同时也表示i这个位置的最长相等前后缀就是j
            if(s[j] == s[i])
                j++;

            // 4.i这个位置的最长相等前后缀的长度就是j
            next[i] = j;
        } 
    }

3.最终代码

class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        if(needle.size() == 0)
            return 0;

        int next[needle.size()];   // 新建next数组变量
        getNext(next, needle);     // 计算前缀表 
        int j = 0;   // needle数组中的索引
        // i是haystack数组中的索引
        for(int i = 0; i < haystack.size(); i++)
        {
            // 只要当前位置的字符不匹配，needle数组索引就根据next数组调到之前匹配的地方继续匹配
            while(j > 0 && haystack[i] != needle[j])
                j = next[j-1];
            
            // 当前位置匹配，needle数组索引向后一位，继续匹配下一位
            if(haystack[i] == needle[j])
                j++;
            
            // 如果needle数组已经遍历完成，则说明找到匹配的子串
            if(j == needle.size())
                return (i - needle.size() + 1);  // i - (needle.size()-1)
        }
        return -1;
    }

private:
    void getNext(int* next, const string& s)
    {
        // 1.初始化
        int j = 0;     // 前缀字符串末尾
        next[0] = 0;   // 第一个位置的最长相等前后缀一定是0

        // 遍历这个字符串，求前缀表
        for(int i = 1; i < s.size(); i++)
        {
            // 2.前后缀字符不相等，使用KMP的思想回退前缀字符的尾指针，直到和后缀字符匹配上
            while(j > 0 && s[j] != s[i])
                j = next[j-1];
            
            // 3.前后缀字符相等，则前缀指针后移，同时也表示i这个位置的最长相等前后缀就是j
            if(s[j] == s[i])
                j++;

            // 4.i这个位置的最长相等前后缀的长度就是j
            next[i] = j;
        } 
    }
};