---
# System prepended metadata

title: 'KMP算法 前綴表 j = next[j-1]之理解'

---

# KMP算法 前綴表 j = next[j-1]之理解


```cpp=
while (j > 0 && s[i] != s[j]) { 
    j = next[j - 1]; 
}
```
過程如下演示

```python=
s = "AAEBAAAAEBAAGAAEBAAAAEBAAE"
     ^^^^^^^^^^^^ ^^^^^^^^^^^^
                 j            i
```
此時G與E不匹配，可以利用next[j-1]找出j之前字串的最大公共前後綴
讓範圍縮小，看看前面部分和後面部分能不能配對起來


j = next[j-1] 即

```python=
s = "AAEBAAAAEBAAGAAEBAAAAEBAAE"
     ^^^^^^             ^^^^^^
           j                  i
```
發現A不等於E，配對不起來，只好再次限縮範圍，試圖尋找可能解
再次執行j = next[j-1]
```python=
s = "AAEBAAAAEBAAGAAEBAAAAEBAAE"
     ^^                     ^^
       j                      i
```
此時E等於E 找到長度為3的最大公共前後綴AAE