已知模式串t=babab主串s=abacbababa。写出t串的next数组和KMP算法下s串与t串的匹配过程

Next 数组的计算过程如下：

- 首先将 t 串的第一个字符位置设为 i，后一个字符位置设为 j。
- 如果 t[i] == t[j]，则将 next[j] 设为 i + 1，i 和 j 同时右移一位。
- 如果 t[i] != t[j]，则先将 i 位置左移，直到 t[i] == t[j] 或者 i 移到了 t 串的第一个字符位置，如果找到了 t[i] == t[j]，则将 next[j] 设为 i + 1，i 和 j 同时右移一位；如果 i 移到了第一个字符位置，那么 next[j] 为 0，j 向右移动一位。

根据计算出来的 next 数组，可以使用 KMP 算法进行字符串匹配。具体的匹配过程如下：

- 首先将主串 s 的第一个字符位置设为 i，模式串 t 的第一个字符位置设为 j。
- 如果 s[i] == t[j]，则 i 和 j 同时右移一位。
- 如果 s[i] != t[j]，则将模式串 t 的位置左移，找到最大的符合条件的位置 k，即 k 为满足 t[k] == s[i] 的最大 k 值。将模式串 t 向右移动 j - next[j] 个字符，重新从 s[i] 和 t[next[j]] 位置开始比较。
- 如果在某一次比较中，模式串 t 的所有字符都匹配成功了，即 j 移动到了模式串 t 的最后一个字符位置，那么说明 s 中存在一个与 t 完全相同的子串，返回匹配的起始位置 i - j + 1。

在本题中，模式串 t=babab 的 next 数组为 [0, 0, 1, 2, 3]。第一次匹配 s 串的第一个字符 a 与 t 串的第一个字符 b 不匹配，因此将 t 串整体向右移动一位，变成了 ababa，此时再与 s 的第一个字符 a 进行匹配，可以成功匹配，因此 j 和 i 都向右移动一位，此时 j=1，i=2。接着又有 s[i] 和 t[j] 不匹配，因此将 t 串整体向右移动 1 位，变成了 babab，此时 next[j]=0，因此将 j 向右移动 1 位，i 不变，此时 j=2，i=2，继续比较 s[i] 和 t[j]，又不匹配，以此类推，直到匹配成功。

笑话：为什么狗不会发微信？ 因为会把手机啃坏。