概述

我现在的理解是，KMP是对暴力算法的优化，而暴力的解法思路是很清晰的。
KMP算法最重要的是每当出现字符串匹配失败时，不移动主字符串的指针，而只移动匹配字符串的指针，并且尽可能的保留已经匹配过的数据，减少指针移动的次数。
根据匹配的字符串，可以计算出每个字符匹配错误的时候，匹配的字符串可以往前移动多少，即从这个位置之前匹配的字符串后缀和匹配字符串的前缀重合的字符有几个，即next数组。
因此，next[j]的含义是，匹配字符串前j个字符中，前缀和后缀匹配的最大长度。

next数组计算

根据数学归纳法，其实总共有两种情况。

  1. 初始值，next[0] = 0。

  2. i从1开始，j从0开始，对比匹配字符串的P[i]和P[j]是不是相等的，如果不是相等的，已经匹配过的长度为j，需要按照j = next[j - 1]进行回退，一直回退到字符相等或者j为0；如果相等的，那么前缀和后缀重合的字符串长度++，即j++，此时j指针不动，只移动i进行下一个字符的匹配。

    字符串匹配

  3. i从0开始，j从0开始，对比主字符串和匹配字符串是不是相等的，如果不是相等的，已经匹配的长度为j，需要按照j = next[j - 1]进行回退，一直回退到字符相等或者j为0；如果相等的，重复的字符串长度++，即j++。

  4. 如果重复的字符串长度等于匹配字符串的长度，则说明匹配成功。

    代码

    下标从1开始

    ```cpp

    include

    using namespace std;

define N 100010

define M 1000010

char P[N]; char S[M]; int nex[N];

int main() { int n, m; while(scanf(“%d”, &n) != EOF ) { cin >> P; scanf(“%d”, &m); cin >> S; // 计算next数组的值 for(int i = 2, j = 0; i <= n; i ++) { // 判断j能否继续向前，不能向前则回退到前一个需要匹配的位置，以此类推，直到j=0或者P[i] = P[j + 1] // i表示现在要求的next的索引值，j表示到索引值为i的时候，前面有多少个重复的字符 while(j && P[i] != P[j + 1]) j = nex[j];

  1.         // 判断重复的字符是否增多
  2.         if (P[i] == P[j + 1]) j++;
  4.         //赋值next[i]
  5.         nex[i] = j;
  6.     }
  8.     // 字符串匹配
  9.     for(int i = 1, j = 0; i < m; i ++) {
  10.         // 判断j能否继续向前，不能向前则回退到前一个需要匹配的位置，以此类推，直到j=0或者S[i] = P[j + 1]
  11.         // i表示现在要匹配的字符索引，j表示到索引值为i的时候，前面有多少个重复的字符
  12.         while(j && S[i] != P[j + 1]) j = nex[j];
  14.         // 判断重复的字符是否增多
  15.         if(S[i] == P[j + 1]) j ++;
  17.         // 匹配完成
  18.         if(j == n) {
  19.             printf("%d ", i - n + 1);
  20.             j = nex[j];
  21.         }
  22.         // printf("%c %d; ", S[i], j);
  23.     }
  24. }
  25. return 0;

}

<a name="eX50P"></a>
#### 下标从0开始
```cpp
#include <iostream>
using namespace std;

#define N 100010
#define M 1000010

int main() {
    int n, m;
    while(scanf("%d", &n) != EOF ) {
        char P[N];
        char S[M];
        int nex[N];
        cin >> P;
        scanf("%d", &m);
        cin >> S;

        // 计算next数组的值
        nex[0] = 0;
        for(int i = 1, j = 0; i < n; i ++) {
            // 判断j能否继续向前，不能向前则回退到前一个需要匹配的位置，以此类推，直到j=0或者P[i] = P[j]
            // i表示现在要求的next的索引值，j表示到索引值为i的时候，前面有多少个重复的字符
            while(j && P[i] != P[j]) j = nex[j - 1];

            // 判断重复的字符是否增多
            if (P[i] == P[j]) j++;

            //赋值next[i]
            nex[i] = j;
        }

        // 字符串匹配
        for(int i = 0, j = 0; i < m; i ++) {
            // 判断j能否继续向前，不能向前则回退到前一个需要匹配的位置，以此类推，直到j=0或者S[i] = P[j]
            // i表示现在要匹配的字符索引，j表示到索引值为i的时候，前面有多少个重复的字符
            while(j && S[i] != P[j]) j = nex[j - 1];

            // 判断重复的字符是否增多
            if(S[i] == P[j]) j ++;

            // 匹配完成
            if(j == n) {
                printf("%d ", i - n + 1);
                j = nex[j - 1];
            }
            // printf("%c %d; ", S[i], j);
        }
    }
    return 0;
}