第十八章 动态规划和KMP算法
一、动态规划
1.介绍
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20 世纪 50 年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解
动态规划当中包含三个重要的概念：
- 最优子结构
- 边界
- 状态转移公式
动态规划解决问题的过程分为两步：
- 寻找状态转移方程式
- 利用状态转移方程式自底向上求解问题
1.爬楼问题
题干
有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上 1 级或者 2 级台阶。要求用程序来求出一共有多少种走法
暴力枚举
利用排列组合，写一个多层嵌套循环，遍历出所有可能性
时间复杂度为指数级
动态规划
最后一步到第 10 级阶梯有两种情况，分别是从第 8 级走两步和从第 9 级走一步
只差一步到第 9 级阶梯有两种情况，分别是从第 7 级走两步和从第 8 级走一步
只差一步到第 8 级阶梯有两种情况，分别是从第 6 级走两步和从第 7 级走一步
……
……
只差一步到第 3 级阶梯有两种情况，分别是从第 1 级走两步和从第 2 级走一步
只差一步到第 2 级阶梯有两种情况，分别是从第 0 级走两步和从第 1 级走一步
只差一步到第 1 级阶梯只有一种情况，即从第 0 级走一步
从上我们可以总结出规律：
F(10) = F(9) + F(8)
F(9) = F(8) + F(7)
…
…
F(2) = F(1) + F(0)
F(1) = 1
F(n) = F(n - 1) + F(n-2) 就是介绍中说的状态转移方程，是动态规划的核心，决定了问题的每一个阶段和下一阶段的关系
当只有 1 级阶梯或者 2 级阶梯的时候，我们可以直接得出结果，我们称 F(1) 和 F(2) 为问题的边界，如果问题没有边界，那么也就无法得到有限的结果
F(10) = F(9) + F(8)，因此 F(9) 和 F(8) 是 F(10) 的最优子结构
接下来就是写代码求解问题
方法一：递归求解
package com.sisyphus.dynamicprogramming;
/**
* @Description: 爬楼问题$
* @Param: $
* @return: $
* @Author: Sisyphus
* @Date: 7/28$
*/
public class Stairs {
public static void main(String[] args) {
System.out.println(stair(10));
}
private static int stair(int n){
if (n < 1){
return 0;
}else if (n == 1){
return 1;
}else if (n == 2){
return 2;
}
return stair(n - 1) + stair(n - 2);
}
}
时间复杂度为 O(2^n)
方法二：备忘录算法
方法一中，我们递归的时候进行了很多重复计算，比如
如果计算 F(3)，我们要计算 F(2) 和 F(1)，在计算 F(2) 的时候又计算了 F(1)
如果计算 F(4)，我们要计算 F(3) 和 F(2)，在计算 F(3) 的时候又计算了 F(2)……
…………
后面还要计算 F(n)，因此可想可知进行了多少次没必要的重复运算
因此我们可以利用缓存将 F(n)~F(1) 的计算结果存入哈希表，再次遇到相同算式时就从哈希表里取出，这样就不用重复计算了
package com.sisyphus.dynamicprogramming;
import java.util.HashMap;
/**
* @Description: 爬楼问题$
* @Param: $
* @return: $
* @Author: Sisyphus
* @Date: 7/28$
*/
public class Stairs {
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap<>();
System.out.println(stair(10, map));
}
private static int stair(int n, HashMap<Integer, Integer> map){
if (n < 1){
return 0;
}else if (n == 1){
return 1;
}else if (n == 2){
return 2;
}
if(map.containsKey(n)){
return map.get(n);
}else {
int value = stair(n - 1,map) + stair(n - 2,map);
map.put(n,value);
return value;
}
}
}
时间复杂度为 O(n)，空间复杂度为 O(n)
方法三：动态规划求解
方法二中，我们可以通过记录 F(n)~F(1) 的计算结果来降低时间复杂度
那我们再进一步思考，知道了 F(1) 和 F(2)，就可以知道 F(3)，那 F(4) 也知道了。F(4) 知道了，F(5) 不是也知道了？
那么我们为什么一定要从最难的 F(n) 向下递归呢？我们直接从 F(3) 开始向上递推不是更加简单？
package com.sisyphus.dynamicprogramming;
import java.util.HashMap;
/**
* @Description: 爬楼问题$
* @Param: $
* @return: $
* @Author: Sisyphus
* @Date: 7/28$
*/
public class Stairs {
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap<>();
System.out.println(stair(10, map));
}
private static int stair(int n, HashMap<Integer, Integer> map){
if (n < 1){
return 0;
}else if (n == 1){
return 1;
}else if (n == 2){
return 2;
}
int a = 1;
int b = 2;
int temp = 0;
for (int i = 3; i <= n ; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
}
时间复杂度为 O(n)，空间复杂度为 O(1)
但这只是针对这单一的一个题目，而且这只是动态规划里最简单的情况，对于其他题目的复杂情况需要进行更多思考，可能这一种方法并不一定比方法一更好
2.扔鸡蛋问题
题干
有 2 个鸡蛋，从 100 层楼上往下扔，如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？比如鸡蛋在第 9 层没有摔碎，在第 10 层摔碎了，那么鸡蛋不会摔碎的临界点就是 9 层（鸡蛋碎了就不可以再次使用了，反之，鸡蛋没碎就可以继续使用）
暴力枚举
为了防止鸡蛋碎了无法继续使用，因此小心翼翼地从第 1 层开始扔鸡蛋，那么最坏的情况就是在第 100 层碎了
但是这样我们就浪费了 1 个鸡蛋，因为完成暴力枚举只需要 1 个鸡蛋
二分查找
我们只有两个鸡蛋，因此我们只能先在 50 层丢第一个鸡蛋，如果碎了还是只能从 第 1 层开始扔鸡蛋（因为只剩这一个了，最坏的情况是在 49 层没碎），如果没碎我们就从第 51 层开始扔，最坏的情况是在 100 层碎了
这与传统的二分查找不同，传统的二分查找由于没有查找次数的限制，可以无限二分，所以效率很高
但是如果限制了查找次数只有两次，二分查找就没有那么好用了
第一枚鸡蛋和第二枚鸡蛋地尝试次数十分不均衡，第一次直接排除了 50 种可能，而后续只能一种一种地进行排除
平方根法
做一个平方根运算，100 的平方根为 10
我们尝试每 10 层 扔一次，因为我们只有两个鸡蛋，所以每一次都得小心，所以第一次从最低的第 10 层扔，第二次从第 20 层扔，……，一直到第 100 层
这样最好的情况是在第 10 层碎掉，我们只需要从 1 扔到 9 就可以了，尝试次数为 1 + 9 = 10
最坏的情况是在第 100 层碎掉，我们只需要从 91 扔到 99 就可以了，再加上前面 10 次，尝试次数为 10 + 9 = 19
这里还有一个小小的优化点，我们可以从 15 层开始扔，接下来从 25 层、35 层扔，……，一直到第 95 层
这样如果在 15 层碎了，我们的尝试次数为 1 + 14 = 15，虽然比优化前尝试次数多了，但其余的情况没有改变
并且，评判一个算法的时间复杂度一般是看最差时间复杂度，那么经过优化后，最坏的情况是在第 95 层碎掉，尝试次数减少为 9 + 9 = 18
解方程法
假设问题存在最优解，这个最优解的最坏情况尝试次数为 X，那么我们第一次扔鸡蛋，就应该选在第 X 层
这个结论是怎么来的呢？听我给你解释一下，你就豁然开朗了
无论我们从哪一层开始扔鸡蛋，鸡蛋永远有两种结果，碎了和没碎
如果碎了，就说明临界点在更低的楼层，我们就需要向下找
如果没碎，就说明临界点在更高的楼层，我们就需要向上找
无论我们采取什么方法，最坏情况永远都有两种
根据平方根法的推演
如果第一次没碎，我们需要继续向上找，越往上需要的尝试次数越多，最坏的情况是 19 或者 18 次
如果第一次碎了，我们就需要向下找，最坏的情况是再找 X - 1 次
假设第一次从 X+n 层扔，那么如果碎了，我们就要尝试 1+X+n-1 = X+n 次，超出最坏情况尝试次数 X
假设第一次从 X-n 层扔，那么如果碎了，我们就要尝试 1+X-n-1 = X-n 次，但是我们显然可以从更高的楼层往下扔，这样就能排除更多的可能，从而减少尝试次数，只有一个前提条件，就是不要超过 X 层
那么我们从 X 层扔就是最好的策略
这样问题就变成了：让两个鸡蛋从 100 层往下扔，要求尝试次数不得超过 X
经过第一次尝试，我们将范围缩减到 100-X 层，但是尝试次数也减少了一次，最多只能尝试 X-1 次，因为我们不能让总尝试次数超出 X
那么问题就可以转换成：让两个鸡蛋从 100-X 层往下扔，要求尝试次数不得超过 X-1
在这个问题下，第二个鸡蛋就应该从第 X-1 层开始扔，总层数是第 X+X-1 层
第三次是第 X+（X-1）+（X-2）层
第四次是第 X+（X-1）+（X-2）+（X-3）层
……
最后一次尝试是第 100 层，用方程表示：X+（X-1）+（X-2）+…+ 1 = 100
化简为 （X + 1）× X / 2 = 100
结果向上取整，得到 X = 14
因此最优解在最坏情况的尝试次数为 14，第一次扔鸡蛋的楼层为 14 层
扩展问题
总共有 M 层楼，N 个鸡蛋，找到临界点要尝试几次？
动态规划
假设有三个鸡蛋，100层楼，第一个鸡蛋扔在第10层并摔碎了。这时候我们还剩下两个鸡蛋，因此第二个鸡蛋不必从底向上一层一层扔，而是可以选择在第5层扔。如果第二个鸡蛋也摔碎了，那么第三个鸡蛋才需要老老实实从第1层开始一层一层扔
这样一来，总的尝试次数是1+1+4 = 6 < 10。
因此，最优解的最坏情况下尝试次数是 X，鸡蛋首次扔出的楼层也是 X 这个规律不再成立
我们可以把 M 层楼 / N 个鸡蛋的问题转化成一个函数 F(M,N)，其中楼层数 M 和鸡蛋数 N 是函数的两个参数，而函数的值则是最优解的最大尝试次数
假设我们第一个鸡蛋扔出的位置在第 X 层（1 <= X <= M）,会出现两种情况：
- 第一个鸡蛋没碎
那么剩余 M-X 层楼，N 个鸡蛋，可以转变为：F(M-X,N) + 1,1 <= X <= M - 第一个鸡蛋碎了
那么只剩下从 1 层到 X-1 层楼需要尝试，剩余 N-1 个鸡蛋，可以转变为：F(X-1,N-1) + 1，1 <= X <= M
整体而言，我们要求出的是 M 层楼在 N 个鸡蛋的条件下，最大尝试次数最小的解
所以这个题目的状态转移方程式如下：
F(M,N) = Min（Max（ F(M-X), N）+ 1 , F(X-1, N-1) + 1 ），1 <= X <= M
诚然，我们有了状态转移方程，就可以用递归的方式来实现，但是递归的时间复杂度是指数级的，当 M 和 N 的值很大的时候，递归的效率会变得非常低
根据动态规划的思想，我们可以自底向上来计算出方程式的结果
我们以 3 个鸡蛋，4 层楼的情况为例，在空格内填入最优尝试次数
根据动态规划的转移方程式和自底向上的求解思路，我们需要从 1 个鸡蛋 1 层楼的最优尝试次数，一步一步推导后续的状态，直到计算出 3 个鸡蛋 4 层楼的尝试次数为止
首先我们把 1 个鸡蛋的那一行填好，因为只有 1 个鸡蛋，所以只能一层一层尝试，所以每层的最优尝试次数就是楼层数
然后把 1 层楼那一列填好，因为只有 1 层，所以无论多少鸡蛋，都只要尝试 1 次即可
2 个鸡蛋 2 层楼的情况，我们就需要带入状态转移方程了：
F（2,2） = Min（Max（ F（2-X，2）+ 1， F（X-1，2-1） + 1）），1<=X<=2
X=1 时，
F（2,2）
= Max（ F（2-1，2）+ 1， F（1-1，2-1） + 1））
= Max（ F（1，2）+ 1， F（0，1） + 1）
= Max（1+1, 0+1）
= 2
X = 2 时，
F（2,2）
= Max（ F（2-2，2）+ 1， F（2-1，2-1） + 1））
= Max（ F（0，2）+ 1， F（1，1） + 1）
= Max（0+1, 1+1）
= 2
因此，无论第一个鸡蛋先从第 1 层扔，还是先从第 2 层扔，结果都是尝试 2 次
2 个鸡蛋 3 层楼的情况，X 的取值是 1，2，3
经过计算，最优的方法是：第一个鸡蛋在第 2 层扔，尝试次数为 2
依照上面的方式，我们计算出 2 个鸡蛋 4 层楼的最优尝试次数，结果是 3 次
同理，我们按照上面的方式，计算出3个鸡蛋在各个楼层的尝试次数，分别是 2 次，2 次， 3次
package com.sisyphus.dynamicprogramming;
/**
* @Description: 鸡蛋问题$
* @Param: $
* @return: $
* @Author: Sisyphus
* @Date: 7/28$
*/
public class Egg {
public static void main(String[] args) {
System.out.println(egg(2,100));
}
private static int egg(int eggNum, int floorNum){
if (eggNum < 1 || floorNum < 1){
return 0;
}
//备忘录，存储 eggNum 个鸡蛋，floorNum 层楼的条件下的最少尝试次数
int[][] cache = new int[eggNum+1][floorNum+1];
//把备忘录每个元素初始化成最大的尝试次数
for(int i = 1; i <= eggNum; i++){
for (int j = 1; j <= floorNum; j++) {
cache[i][j] = j;
}
}
for (int n = 2; n <= eggNum; n++) {
for (int m = 1; m <= floorNum; m++) {
for (int k = 1; k <= m; k++) {
//扔鸡蛋的楼层从 1 到 吗 枚举一遍
//如果当前算出的尝试次数小于上一次算出的尝试次数
//则取代上一次的尝试次数
//这里可以打印 k 的值，从而知道第一个鸡蛋是从第几次扔的
cache[n][m] = Math.min(cache[n][m], 1+Math.max(cache[n-1][k-1],cache[n][m-k]));
}
}
}
return cache[eggNum][floorNum];
}
}
时间复杂度为 O(MMN)，空间复杂度为 O(M*N)
我们还可以进一步优化
我们从状态转移方程式以及上面的表格可以看出，每一次中间状态的尝试次数，都只和上一层（鸡蛋数量 - 1）和本层（当前鸡蛋数量）的值有关联
比如我们想要求解 3 个鸡蛋 3 层楼的最优尝试次数，并不需要知道 1 个鸡蛋这一层的值，只需要关心 2 个鸡蛋和 3 个鸡蛋在各个楼层的值即可
这样一来，我们并不需要一个二维数组来存储完整的中间状态记录，只需要利用两个一维数组，存储上一层和本层的尝试次数就足够了
package com.sisyphus.dynamicprogramming;
/**
* @Description: 鸡蛋问题$
* @Param: $
* @return: $
* @Author: Sisyphus
* @Date: 7/28$
*/
public class Egg {
public static void main(String[] args) {
System.out.println(egg(2,100));
}
private static int egg(int eggNum, int floorNum) {
if (eggNum < 1 || floorNum < 1) {
return 0;
}
//上一层备忘录，存储（鸡蛋数量 - 1）的 floorNum 层楼条件下的最少尝试次数
int[] preCache = new int[floorNum + 1];
//备忘录，存储 eggNum 个鸡蛋，floorNum 层楼的条件下的最少尝试次数
int[] currentCache = new int[floorNum + 1];
//把备忘录每个元素初始化成最大的尝试次数
for (int i = 1; i <= floorNum; i++) {
currentCache[i] = i;
}
for(int n=2; n<=eggNum; n++){
//当前备忘录拷贝给上一次备忘录，并重新初始化当前备忘录
preCache = currentCache.clone();
for(int i=1;i<=floorNum; i++){
currentCache[i] = i;
}
for(int m=1; m<=floorNum; m++){
for(int k=1; k<m; k++){
//扔鸡蛋的楼层从 1 到 m 枚举一遍，如果当前算出的尝试次数小于上一次算出的尝试次数，则取代上一次的尝试次数。
//这里可以打印 k 的值，从而知道第一个鸡蛋是从第几次扔的。
currentCache[m] = Math.min(currentCache[m], 1+Math.max(preCache[k-1],currentCache[m-k]));
}
}
}
return currentCache[floorNum];
}
}
时间复杂度不变，空间复杂度度为 O(M)
3.背包问题
题干
有四个物品，背包总容量为 8，背包最多能装入价值为多少的物品？
| 物品编号 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 物品体积 | 2 | 3 | 4 | 5 |
| 物品价值 | 3 | 4 | 5 | 6 |
填表
寻找状态转移方程：
- 如果装不下当前物品，那么前 n 个物品的最佳组合和前 n - 1 个物品的最佳组合是一样的
- 如果装得下当前物品
（1）装当前物品，在给当前物品预留了相应空间的情况下，前 n - 1 个物品的最佳组合加上当前物品的价值就是总价值
（2）不装当前物品，那么前 n 个物品的最佳组合和前 n - 1 个物品的最佳组合是一样的
选取（1）和（2）中价值较大的，为当前最佳组合
package com.sisyphus.dynamicprogramming;
/**
* @Description: 背包问题$
* @Param: $
* @return: $
* @Author: Sisyphus
* @Date: 7/27$
*/
//有 N 件物品和一个容量为 V 的背包
// 第 i 件物品的体积是 C[i]，价值是 W[i]
public class KnapsackProblem {
public static void main(String[] args) {
int[] C = {2,3,4,5};
int[] W = {3,4,5,6};
System.out.println("最大价值："+zeroOnePack(8,C,W));
}
/**
*
* @param V 背包容量
* @param C 物品体积
* @param W 物品价值
* @return
*/
private static int zeroOnePack(int V, int[] C, int[] W){
//防止无效输入
if ((V <= 0) || (C.length != W.length)){
return 0;
}
int[] dp = new int[V + 1];
for (int i = 0; i < C.length; i++) {
for (int j = V; j >= C[i]; --j) {
dp[j] = Math.max(dp[j],dp[j - C[i]] + W[i]);
}
}
return dp[V];
}
}
问题进阶
原题中，物品只能被选择 1 次，或者 0 次，因此我们称之为 01 背包问题
那如果物品可以被选择多次呢？这类问题我们称为完全背包问题
解法：
在 01 背包中，状态 dp[i][j] 依赖的是 dp[i-1][j]
而完全背包中，状态 dp[i][j] 依赖的是 dp[i-1][j] 以及 dp[i][k]，k < j
package com.sisyphus.dynamicprogramming;
/**
* @Description: 背包问题$
* @Param: $
* @return: $
* @Author: Sisyphus
* @Date: 7/27$
*/
//有 N 件物品和一个容量为 V 的背包
// 第 i 件物品的体积是 C[i]，价值是 W[i]
public class KnapsackProblem {
public static void main(String[] args) {
int[] C = {2,3,4,5};
int[] W = {3,4,5,6};
System.out.println("最大价值："+completePack(8,C,W));
}
/**
*
* @param V 背包容量
* @param C 物品体积
* @param W 物品价值
* @return
*/
private static int zeroOnePack(int V, int[] C, int[] W){
//防止无效输入
if ((V <= 0) || (C.length != W.length)){
return 0;
}
int[] dp = new int[V + 1];
for (int i = 0; i < C.length; ++i) {
for (int j = V; j >= C[i]; --j) {
dp[j] = Math.max(dp[j],dp[j - C[i]] + W[i]);
}
}
return dp[V];
}
private static int completePack(int V, int[] C, int[] W){
//防止无效输入
if ((V <= 0) || (C.length != W.length)){
return 0;
}
int[] dp = new int[V + 1];
for (int i = 0; i < C.length; ++i) {
for (int j = C[i]; j <= V; ++j) {
dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
}
}
return dp[V];
}
}
二、KMP算法
1.引入
暴力匹配算法(BruteForce)
暴力匹配算法的思路很简单，用模式串的第一个字符和主串的第一个字符比较，如果相等就用模式串的第二个字符和主串的第二个字符比较，如果不相等就用子串的第一个字符和主串的第二个字符比较，以此类推
package com.sisyphus.knuthmorrispratt;
/**
* @Description: 暴力匹配算法$
* @Param: $
* @return: $
* @Author: Sisyphus
* @Date: 7/27$
*/
public class BruteForce {
public static void main(String[] args) {
String str1 = "223 123412 123412341245";
String str2 = "1234124";
int index = bruteForce(str1,str2);
System.out.println("index=" + index);
}
//暴力匹配算法实现
public static int bruteForce(String str1, String str2) {
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
int s1Len = s1.length;
int s2Len = s2.length;
int i = 0; //i 索引指向 s1
int j = 0; //j 索引指向 s2
while (i < s1Len && j < s2Len) { //保证匹配时不越界
if (s1[i] == s2[j]) { //匹配成功
i++;
j++;
} else {
i = i - (j - 1);
j = 0;
}
}
//判断是否匹配成功
if (j == s2Len) {
return i - j;
} else {
return -1;
}
}
}
暴力匹配算法的缺点很明显，效率实在是太低了，每一轮只能老老实实地把模式串右移一位，实际上做了很多无谓的比较
而 KMP 算法的目标就是让模式串在每一轮尽量向后多移动几位，从而减少无谓的比较
2.介绍
KMP 算法（The Knuth-Morris-Pratt Algorithm）是一种改进的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next() 函数实现，函数本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度 O(m+n)
整体思路
第一轮，模式串和主串的第一个等长子串比较，发现前 5 个字符都是匹配的，第 6 个字符不匹配，是一个 “坏字符”：
我们可以发现，在前缀 “GTGTG” 当中，后三个字符 “GTG” 和前三位字符 “GTG” 是相同的。在下一轮的比较时，只有把这两个相同的片段对齐，才有可能出现匹配。这两个字符串片段，分别叫做最长可匹配后缀子串和最长可匹配前缀子串
第二轮，我们直接把模式串向后移动两位，让两个“GTG”对齐，继续从刚才主串的坏字符A开始进行比较
显然，主串的字符A仍然是坏字符，这时候的匹配前缀缩短成了GTG
按照第一轮的思路，我们来重新确定最长可匹配后缀子串和最长可匹配前缀子串：
第三轮，我们再次把模式串向后移动两位，让两个“G”对齐，继续从刚才主串的坏字符A开始进行比较
以上就是KMP算法的整体思路：在已匹配的前缀当中寻找到最长可匹配后缀子串和最长可匹配前缀子串，在下一轮直接把两者对齐，从而实现模式串的快速移动
然而找到一个字符串前缀的【最长可匹配后缀子串】和【最长可匹配前缀子串】生成 next 数组才是 KMP 算法的最大难点
next 数组
next 数组是一个一维整形数组，数组的下标代表了 “已匹配前缀的下一个位置” ，元素的值则是 “最长可匹配前缀子串的下一个位置”
有了next数组，我们就可以通过已匹配前缀的下一个位置（坏字符位置），快速寻找到最长可匹配前缀的下一个位置，然后把这两个位置对齐
比如下面的场景，我们通过坏字符下标5，可以找到 next[5]=3，即最长可匹配前缀的下一个位置：
next 数组的生成方法
我们可以采用类似 “动态规划” 的方法。首先 next[0] 和 next[1] 的值肯定是 0 ，因为这时候不存在前缀子串
从 next[2] 开始，next 数组的每一个元素都可以由上一个元素推导而来
下面演示一下如何推导：
如图所示，我们设置两个变量 i 和 j，其中 i 表示 “已匹配前缀的下一个位置”，也就是待填充的数组下标，j 表示 “最长可匹配前缀子串的下一个位置” ，也就是待填充的数组元素值
当以匹配前缀不存在的时候，最长可匹配前缀子串当然也不存在，所以 i = 0，j = 0，此时 next[0] = 0
接下来，我们让已匹配前缀字串的长度加 1：
此时的已匹配前缀是 G ，由于只有一个字符，同样不存在最长可匹配前缀子串，所以 i = 1，j = 0，next[i] = 0
接下来，我们让已匹配前缀字串的长度继续加 1：
此时的已匹配前缀是 GT，我们需要开始做判断了：由于模式串当中 pattern[j] != pattern[i-1]， G != T，最长可匹配前缀子串仍然不存在
所以当 i = 2 时，j 仍然是 0，next[2] = 0
接下来，我们让已匹配前缀子串的长度继续加 1
此时的已匹配前缀是 GTG，由于模式串当中 pettern[j] = pattern[i-1]，即 G = G，最长可匹配前缀子串出现了，是 G
所以当 i = 3 时，j = 1，next[3] = next[2] + 1 = 1
接下来，我们让已匹配前缀字串的长度继续加 1
此时的已匹配前缀是GTGT，由于模式串当中 pattern[j] = pattern[i-1]，即T=T，最长可匹配前缀子串又增加了一位，是GT
所以当i=4时，j=2，next[4] = next[3]+1 = 2
接下来，我们让已匹配前缀子串的长度继续加 1
此时的已匹配前缀是 GTGTG，由于模式串当中 pattern[j] = pattern[i-1]，即 G=G，最长可匹配前缀子串又增加了一位，是 GTG
所以当 i = 5 时，j = 3，next[5] = next[4] + 1 = 3
接下来，我们让已匹配前缀子串的长度继续加 1
此时的已匹配前缀是GTGTGC，这时候需要注意了，模式串当中 pattern[j] ！= pattern[i-1]，即T != C
这时候，我们已经无法从 next[5] 的值来推导出 next[6]，而字符 C 的前面又有两段重复的子串 “GTG”。那么，我们可以尝试着把问题转化一下。把计算 “GTGTGC” 最长可匹配前缀子串的问题，转化成计算 “GTGC” 最长可匹配前缀子串的问题
这样的问题转化，也就相当于把变量j回溯到了next[j]，也就是j=1的局面（i 值不变）
回溯后，情况仍然是 pattern[j] ！= pattern[i-1]，即 T！=C。那么我们可以把问题继续进行转化
问题再次的转化，相当于再一次把变量j回溯到了next[j]，也就是 j=0 的局面
回溯后，情况仍然是 pattern[j] ！= pattern[i-1]，即 G！=C。j已经不能再次回溯了，所以我们得出结论：i=6 时，j=0，next[6] = 0
以上就是next数组元素的推导过程
总结 KMP 算法全过程：
- 对模式串预处理，生成 next 数组
- 进入主循环，遍历主串
2.1 比较主串和模式串的字符
2.2 如果发现坏字符，查询 next 数组，得到匹配前缀所对应的最长可匹配前缀子串，移动模式串到对应位置
2.3 如果当前字符匹配，继续循环
2.代码实现
package com.sisyphus.knuthmorrispratt;
import java.util.Arrays;
/**
* @Description: KMP算法$
* @Param: $
* @return: $
* @Author: Sisyphus
* @Date: 7/27$
*/
public class KnuthMorrisPratt {
public static void main(String[] args) {
String str = "ATGTGAGCTGGTGTGTGCFAA";
String pattern = "GTGTGCF";
int index = knuthMorrisPratt(str,pattern);
System.out.println("首次出现位置：" + index);
}
private static int[] getNext(String pattern){
int[] next = new int[pattern.length()];
int j = 0;
for (int i = 2; i < pattern.length(); i++) {
while( j != 0 && pattern.charAt(j) != pattern.charAt(i-1)){
//从 next[i+1] 的求解回溯到 next[j]
j = next[j];
}
if (pattern.charAt(j) == pattern.charAt(i-1)){
j++;
}
next[i] = j;
}
return next;
}
private static int knuthMorrisPratt(String str, String pattern){
int[] next = getNext(pattern);
int j = 0;
for (int i = 0; i < str.length(); i++) {
while(j > 0 && str.charAt(i) != pattern.charAt(j)){
//遇到坏字符时，查询 next 数组并改变模式串的起点
j = next[j];
}
if (str.charAt(i) == pattern.charAt(j)){
j++;
}
if (j == pattern.length()){
//匹配成功，返回下标
return i - pattern.length() + 1;
}
}
return -1;
}
}
时间复杂度为 O(m+n)，空间复杂度为 O(m)，其中 m 为模式串长度，n 为主串长度