• 28.实现strStr() :::info KMP经典题目
      当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。 ::: KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

    首先理解next数组，前缀表
    前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

    这句话什么意思呢，就是下面这个意思：
    实现strStr() - 图1 :::info 当b跟f不相等的时候，我们知道

    • 模式串f前面和文本串b前面的都相等

    我要通过next数组知道，

    • 此时模式串f前面的字母是否在模式串的最前面出现过
      • 出现过，则出现了多少位置，
        • 跳转到这个数字就是可以继续匹配的地方。
      • 没出现过，则为0，模式串指针跳转到开头 :::

    注意，任何子串都是从左往右读，，没有因为是在后面的子串所以从右往左读。

    那么什么是前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

    • 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串
    • 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。（并不是从右往左数串，依然是从左往右数的串）

    前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

    可以看出模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。
    实现strStr() - 图2

    代码：（详细注释）

    1. //不减1
    2. class Solution {
    3. public:
    4.     void getNext(int* next, const string& s) {
    5.         int j = 0;
    6.         next[0] = 0;
    7.         for(int i = 1; i < s.size(); i++) {
    8.             while (j > 0 && s[i] != s[j]) {
    9.                 j = next[j - 1]; //归零器
    10.             }
    11.             if (s[i] == s[j]) {
    12.                 j++;  // 前后缀相等的进步器
    13.             }
    14.             next[i] = j; //每一步都要赋值
    15.         }
    16.     }
    17.     int strStr(string haystack, string needle) {
    18.         if (needle.size() == 0) {
    19.             return 0;
    20.         }
    21.         int next[needle.size()];
    22.         getNext(next, needle);
    23.         int j = 0;
    24.         for (int i = 0; i < haystack.size(); i++) {
    25.             while(j > 0 && haystack[i] != needle[j]) {
    26.                 j = next[j - 1];
    27.             }
    28.             if (haystack[i] == needle[j]) {
    29.                 j++;
    30.             }
    31.             if (j == needle.size() ) {
    32.                 return (i - needle.size() + 1);
    33.             }
    34.         }
    35.         return -1;
    36.     }
    37. };

    分析：
    可以发现，kmp在构造前缀和查找子串的时候分别都使用到了。
    可以认为，这个子串寻找，就是不停地拿头部字母，与其他字母比较是否相等，如果相等就用进步器计算等了多长，如果不等，就使用归零器归零。