# KMP算法 -- next解釋


## KMP 基本概念
一種用來字符串匹配的算法
一些定義：
1. s[] 為主字串 ， p[] 是匹配串 ， 即可以理解成p是否是s的子字串
2. 前綴：包含首位字符但不包含末位字符的子字串; 後綴：包含末位字符但不包含首位字符的子字串
3. 部分匹配值 ： 前綴與後綴最長共有長度
4. next[] 存的是每個下標對應的部分匹配值

* 核心思考：每次匹配失敗時，把p串往後移動至next對應的值

## next的含義與模擬

字串從1開始存，next[i], 是p[1,i]中前綴和後綴相同的最大長度（部分匹配值）， 定義 next[1] = 0
例如：
```
idx  1 2 3 4 5 6
str  a b c a b a
next 0 0 0 1 2 1
```

求next陣列的code
```c
// m 為 p 的長度
for(int i = 2, j = 0; i <= m; i++)
{
    while(j && p[i] != p[j + 1]) j = ne[j]; //已經有部分匹配值後，且匹配失敗，回退到上一個 
    if(p[i] == p[j + 1]) j++;
    ne[i] = j; // j為要回退的位置
}
```

匹配過程：
```c
for(int i = 1, j = 0; i < n; i ++)
{
    while(j && s[i] != p[j + 1]) j = ne[j];
    if(s[i] == p[j + 1]) j++;
    if(j == m)
    {
        //匹配成功
        j = ne[j]; // 繼續匹配下一個字串
    }
}
```