理解KMP算法

## 是什么？
有道经典算法题：
```
给你一个文本串 T ，一个非空模板串 S ，问 S 在 T 中出现了多少次
数据范围：1≤𝑙𝑒𝑛(𝑆)≤500000,1≤𝑙𝑒𝑛(𝑇)≤1000000
要求：空间复杂度 𝑂(𝑙𝑒𝑛(𝑆))，时间复杂度 𝑂(𝑙𝑒𝑛(𝑆)+𝑙𝑒𝑛(𝑇))
```

我第一次写的答案
```java
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        int n = 0;
        int l = (T.length() - S.length()) + 1;

for (int i = 0; i < l; i++) {
            if (T.startsWith(S,i)) {
                n++;
            }
        }
        return n;
    }
}
```

运行发现时间复杂度太大，速度超过了2s。

这是标准答案
```java
public int kmp(String S, String T) {
    if (S.length() > T.length()) return 0;
    
    // ========== 第一步：预处理模式串 ==========
    int[] next = new int[S.length()];
    // i: 当前字符位置，j: 已匹配的前缀长度（也是下一个要比的位置）
    for (int i = 1, j = 0; i < S.length(); i++) {
        while (j > 0 && S.charAt(i) != S.charAt(j)) {
            j = next[j - 1];  // 失配：回退到次优候选
        }
        if (S.charAt(i) == S.charAt(j)) {
            j++;              // 匹配：扩展前缀
        }
        next[i] = j;          // 记录：S[0..i]的最长公共前后缀长度
    }
    
    // ========== 第二步：KMP匹配 ==========
    int count = 0;
    for (int i = 0, j = 0; i < T.length(); i++) {
        while (j > 0 && T.charAt(i) != S.charAt(j)) {
            j = next[j - 1];  // 失配：S滑动，T不动
        }
        if (T.charAt(i) == S.charAt(j)) {
            j++;              // 匹配：双双前进
        }
        if (j == S.length()) {
            count++;
            j = next[j - 1];  // 成功：保留重叠，继续搜索
        }
    }
    
    return count;
}
```
[scode type="yellow"]光知道代码没用，得理解才行，为什么要这样写。[/scode]

## 怎么做

### 理解next数组的物理意义

> next[i] = 模式串S[0..i]中，最长相等"真前缀"与"真后缀"的长度

| 术语 | 定义 | 例子（S="ababab"） |
|:---|:---|:---|
| 真前缀 | 不包含自身的所有前缀 | "a", "ab", "aba", "abab", "ababa" |
| 真后缀 | 不包含自身的所有后缀 | "b", "ab", "bab", "abab", "babab" |
| 最长相等对 | 同一个字符串既是前缀又是后缀 | "abab"（长度4）|

### 理解next数组的“递推”

> 核心思想：已知`next[i-1]`，如何求`next[i]`？

```
模式串:  a b a b a b c
索引:   0 1 2 3 4 5 6

已知: next[4] = 3  （"ababa"的最长公共前后缀是"aba"）
求:   next[5] = ?  （"ababab"的最长公共前后缀）
```
其实这里我还是没理解递推的含义，所以有了下面这个图：

```
S[0..4] = "ababa"      想扩展成      S[0..5] = "ababab"
   ↑                                    ↑
 前缀"aba" (长度3)                    期望: 前缀"abab" (长度4)
 后缀"aba" (长度3)                    期望: 后缀"abab" (长度4)
  
关键观察：如果 S[3] == S[5]，就能直接扩展！
          （"aba"的下一个字符）  （新字符）
          
即：如果 S[next[4]] == S[5]，则 next[5] = next[4] + 1 = 4
```

这里我终于懂了，如果当前已知的最大公共前后缀的下一位和最后一位相等，那么就产生了一个新的更长的公共前后缀。

### 失配时的“回退”

> 如果不相等怎么办？

```
S = "abacabad"

求 next[6]，已知 next[5]=3（"abacab"的"abab"? 不对，重新算...）

让我重新来：S="abacabad"
索引: 0 1 2 3 4 5 6 7
字符: a b a c a b a d

next[0] = 0  （"a"，无真前后缀）
next[1] = 0  （"ab"，无相等前后缀）
next[2] = 1  （"aba"，"a"="a"）
next[3] = 0  （"abac"，无）
next[4] = 1  （"abaca"，"a"="a"）
next[5] = 2  （"abacab"，"ab"="ab"）
next[6] = 3? （"abacaba"，期望"aba"="aba" → 是！）

现在求 next[7]：S[7]='d'，S[3]='c'，不相等！
```

**怎么回退**：
```
当前: "abacaba" + 'd'
      ↑ 已匹配前缀长度3（"aba"）
      
      "aba" + 'd' 期望匹配 "aba" + 'c'? 不对...
      
      回退到 next[2]=1，即前缀"a"
      "a" + 'd' 期望匹配 "a" + 'b'? 不对...
      
      再回退到 next[0]=0
      "" + 'd'，从头开始，next[7]=0
```

到这里大概明白next数组怎么来的了。
```java
        // ========== 步骤1: 构建next数组 ==========
        int[] next = new int[sLen];
        // next[i] = S[0..i]的最长相等真前缀与真后缀的长度

// 手动设置next[0] = 0（单个字符无真前后缀）
        for (int i = 1, j = 0; i < sLen; i++) {
            // j: 当前已匹配的最长前缀长度，也是下一个要比较的位置

// 失配：回退j到前一个可能的匹配位置
            while (j > 0 && S.charAt(i) != S.charAt(j)) {
                j = next[j - 1];
            }

// 匹配成功：扩展匹配长度
            if (S.charAt(i) == S.charAt(j)) {
                j++;
            }

next[i] = j;
        }
```

在执行MKP匹配的时候类似于next的形成，只不过在j=S.length时回退到S的上一个最大公共子串。记住了next数组的算法KMP的算法也就自然带出了。

## 为什么

| 问题 | 自测 |
|:---|:---|
| 为什么next[0]=0？ | 单个字符没有真前后缀 |
| 为什么匹配成功后j=next[j-1]？ | 保留最长可复用前缀，允许重叠匹配 |
| 为什么失配时j=next[j-1]而不是next[j]？ | next[j]是S[0..j]的，我们要的是S[0..j-1]的 |
| 时间复杂度为什么是O(n)？ | i只进不退，每个字符最多被比较2次（前进+回退），回退总量≤前进总量 |