kmp算法讲解 java

红太狼 2021-09-23 08:38 302阅读 0赞

### 文章目录 ###

*   *  暴力匹配算法
     *  kmp算法
     *   *  next数组
         *   *  暴力求解next数组
             *  求解next数组
         *  kmp算法代码
         *  kmp算法优化

kmp算法本质上就是一个字符串匹配的算法。它的作用与java中String类的indexOf方法是一样的，就是返回一个字符串（ **以下简称N串**）在另一个字符串（ **以下简称M串**）中的位置，其核心也就是找到主字符串中与匹配字符串相同的部分。只不过在复杂度上进行了一些优化。

## 暴力匹配算法 ##

简单来说，就是通过双重循环来遍历所有情况，以进行匹配。  
相信所有正在学习kmp算法的人早已掌握这种方法了，我也不再多说，只给出一种解法以供参考。

public class Test { 
    
    	public static void main(String[] args) { 
    		System.out.println(simple("asdfghM asdfghN", "asdfghN"));
    	}
    	
    	public static int simple(String src, String target){ 
    		for(int i = 0; i < src.length() - target.length() + 1; i++){ 
    			boolean flag = true;
    			for(int j = 0; j < target.length(); j++){ 
    				if(src.charAt(i + j) != target.charAt(j)){ 
    					flag = false;
    					break;
    				}
    			}
    			if(flag){ 
    				return i;
    			}
    			flag = true;
    		}
    		return -1;
    	}
    
    }

## kmp算法 ##

回顾一下之前的暴力匹配算法，它的实际比较过程应该是这样的。

--------第1次比较--------
              a==a
    asdfghM asdfghN
    asdfghN
    --------第2次比较--------
              s==s
    asdfghM asdfghN
    asdfghN
    --------第3次比较--------
              d==d
    asdfghM asdfghN
    asdfghN
    --------第4次比较--------
              f==f
    asdfghM asdfghN
    asdfghN
    --------第5次比较--------
              g==g
    asdfghM asdfghN
    asdfghN
    --------第6次比较--------
              h==h
    asdfghM asdfghN
    asdfghN
    --------第7次比较--------
              M!=N
    asdfghM asdfghN
    asdfghN
    --------第8次比较--------
              s!=a
    asdfghM asdfghN
     asdfghN
    --------第9次比较--------
              d!=a
    asdfghM asdfghN
      asdfghN
    --------第10次比较--------
              f!=a
    asdfghM asdfghN
       asdfghN
    --------第11次比较--------
              g!=a
    asdfghM asdfghN
        asdfghN
    --------第12次比较--------
              h!=a
    asdfghM asdfghN
         asdfghN
    --------第13次比较--------
              M!=a
    asdfghM asdfghN
          asdfghN
    --------第14次比较--------
               !=a
    asdfghM asdfghN
           asdfghN
    --------第15次比较--------
              a==a
    asdfghM asdfghN
            asdfghN
    --------第16次比较--------
              s==s
    asdfghM asdfghN
            asdfghN
    --------第17次比较--------
              d==d
    asdfghM asdfghN
            asdfghN
    --------第18次比较--------
              f==f
    asdfghM asdfghN
            asdfghN
    --------第19次比较--------
              g==g
    asdfghM asdfghN
            asdfghN
    --------第20次比较--------
              h==h
    asdfghM asdfghN
            asdfghN
    --------第21次比较--------
              N==N
    asdfghM asdfghN
            asdfghN

仔细观察，在第7次比较时，`M != N`，然后就将N串向右移一位，重新以第一位进行比较。这很合理，却又太过笨拙。对于N串来说，它的**每一个字符都是不相等的**。在进行第7次比较时，已经确认它的前6个字符与M串一一对应了，换句话说，**N串的第一个字符（a）与M串的2~5的字符（sdfgh）肯定也是不相等的**。所以，第8次比较不应该只向右移一位，而是应该向右移6位，进行上图中的“**第13次比较**”。

**ps**：为什么是向右移6位而不是7位？因为  
N(1) != N(7) && M(7) != N(7) 并不能推导出 N(1) != M(7)

***从上述例子中应该能猜得到，根据N串本身的特点，可以在比较中向右移更多的位数。特殊的，若N串中所有字符都不相等，那么可以向右移当前比较位数减一的位数。***

对于这样的特殊情况，是可以向右移最多的位数的。那么现在要考虑的就是，在什么情况下，不能够向右移这么多的位数。换句话说，当进行第7次比较并且不相等时，**对于之前的6个字符来说，N串只需向右移动某个位数（小于6），即可使N串的前几个字符与M串的前6个字符中的某个子串相等，并且使之有可能存在另一个解**。

这只是一个半成品的推论，它并不能为我们做什么。这是还是拿起笔在纸上写一写吧。

我写了这样一个例子。

asdasea......
    asdaseN

在进行第7次比较后，一定不存在一个移动小于6的位数的解。在通过多次尝试之后，***终于总结出规律：※※※N串的前6位字符必须首尾存在相同子串***。  
写个例子验证一下。

--------第7次比较--------
             M != N
    asdasdM
    asdasdN
    --------第8次比较--------
             M != a
    asdasdM
       asdasdN

**解释：**

*  ***由于N串的前6位是首尾存在长度为3的相同子串的，所以N(1,2,3)一定是等于M(4,5,6)的，所以第8次直接比较M(7)与N(4)。***
 *  ***在第7次比较中，N(7) != M(7)，但是N(4)依然有可能等于M(7)。***

通过上面的规律，可以总结出更一般向的结论：**若N串已经匹配到了第a位（a大于1），并且在a位之前的子串中存在首尾相同的长度为b的子串（若不存在这样的子串，则记b等于0），则可以将N串向右移b位，并且用N(b+1)继续与M串中上一次参与比较的字符进行比较（根据个人习惯，也可以理解成N(a-b)）。**

**ps**: 其实，数学好的同学是可以写出严谨的数学证明来验证这一结论的，我以前也写过，然后，忘了。不过这么直观的东西不用证明也是可以的吧。

现在，问题的关键已经转换到求N串的每一位字符之前的子串中，最长首尾相同子串的长度上了。而这个最长长度所组成的数组，即是**next**数组。

### next数组 ###

先写个例子看一下

asdaseN   
    这个字符串所对应的next数组为
    [-1, 0, 0, 0, 1, 2, 0]

e（第6位）对应的值为2，是因为之前有as这个长度为2的子串。s（第5位）对应的值为1是因为之前有a这个长度为1的子串。至于首位的-1，则可以认为这是人为规定的，因为它之前没有子串。在之后的代码中也会看到，-1被当做一个特殊值使用。毕竟，如果第一个值就不相等，那么肯定是直接向后移一位的。

虽然我们已经知道了next数组的含义，但是想要求出它并不是一件容易事。

#### 暴力求解next数组 ####

遇到复杂的问题总是想暴力求解一下，因为这通常比较简单。但是next数组的暴力求解还是有点复杂的。况且，作为解决暴力搜索字符串复杂度问题的最核心步骤，竟然还是用暴力搜索求解，也显得有些滑稽。

public static int[] getNext1(String target){ 
    		int[] next = new int[target.length()];
    		for(int i = 0; i < target.length(); i++){ 
    			for(int j = 0; j < i; j++){ 
    				//System.out.println(target.substring(0, i));
    				for(int q = j; q > 0; q--){ 
    					//System.out.println("q = " + q + " j = " + j);
    					//System.out.println(target.charAt(j - q) + "--" + target.charAt(i - q));
    					if(target.charAt(j - q) != target.charAt(i - q)){ 
    						break;
    					}
    					if(q == 1){ 
    						next[i] = j;
    					}
    						
    				}
    			}
    			next[i] = i == 0 ? -1 : Math.max(next[i], -1);
    		}
    		return next;
    	}

#### 求解next数组 ####

正确的next数组求解算法要优雅得多。它会以前一位的值作为基础来推算下一位的值，其中会用到递归的写法，更准确的说，这属于一种动态规划。那么首先就是要找到它的推算规则。

**next数组定义：next数组每一位的值，代表之前子串中，首尾最长相同字符串的长度。**

为什么在这里又提了一遍next数组定义？因为这是理解后面算法的核心！

首先，准备一个特征性很强的字符串用作讨论`abaababa` 。  
它对应的next数组应该是这样的

a b a a b a b a
    -1 0 0 1 1 2 3 2

next数组的递推可以分为3种情况

*  **第一种**  
    首位为-1，其他位若没有首位相同字符串，则为0 。这个是终止条件。
 *  **第二种**  
    现在，先假设我们已经求得了它的前6位，即`[-1, 0, 0, 1, 1, 2]` 。  
    当求解第7位时，可以知道它的前一位是2 。next数组的第6位是2，这代表着，  
    N(1)N(2) == N(4)N(5)，因此，现在只需要判断N(3)与N(6)是否相等就可以确定N(7)是否等于3 （用递归的说法就是2 + 1）。在这个例子中，N(3)，N(6)都为1，所以可以直接得出N(7)等于3 。
 *  **第三种**  
    若上述中的N(3)与N(6)不等又会怎样呢？先假设现在已经求出了next数组的前7位，即  
    `[-1, 0, 0, 1, 1, 2, 3]` 。  
    在求解第8位时，依然按照上面的方法求解，但是会发现N(4) ！= N(7)，这时候就需要一个跳跃性思维了：直接观察N(N(7))，即N(3) = 1 。  
    现在的情况是，N(7) = 3,N(3) = 1 。结合着next数组的定义来看，这代表着：  
    **N(1)=N(3)=N(4)=N(6)**  
    不过我们现在需要的只是N(1)=N(6) ，这样就可以只判断N(2)与N(7)是否相等来确定N(8)是否等于2（用递归的角度说就是N(3)+1）。 在本例中，N(2)与N(7)相等，因此N(8)为2 。若不相等，则继续按照此方法递归着找下去，直到找到相等的值，或者找到尽头，即第1位。

靠着上面3个规则，已经可以求出next了。

public static int[] getNext(String target){ 
    		int[] next = new int[target.length()];
    		next[0] = -1;
    		int i = 1;
    		int j = 0;
    		
    		while(i < target.length() - 1){ 
    			if(j == -1 || target.charAt(j) == target.charAt(i)){ 
    				j++;
    				i++;
    				next[i] = j;
    			}else { 
    				j = next[j];
    			}
    		}
    		return next;
    	}

这段代码是上面3种规则的完美体现，相信已经不需要再解释了。

### kmp算法代码 ###

现在已经有了kmp算法的规则和最重要的next求法，剩下的只要组装一下就行了。

/** * @param args */
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		String src = "asdaseM asdaseN";
    		String target = "asdaseN";
    		
    		System.out.println(kmp(src, target));
    	}
    	
    	public static int kmp(String src, String target){ 
    		
    		int[] next = getNext(target);
    			
    		int i = 0;	//src下标
    		int j = 0;	//target下标
    		
    		for(; j < target.length() && i < src.length(); ){ 
    			if(j == -1 || src.charAt(i) == target.charAt(j)){ 
    				i++;
    				j++;
    			}else { 
    				j = next[j];
    			}
    		}
    		
    		if(j == target.length()){ 
    			return i - j;
    		}
    			
    		return -1;
    	}
    
    	public static int[] getNext(String target){ 
    		int[] next = new int[target.length()];
    		next[0] = -1;
    		int i = 1;
    		int j = 0;
    		
    		while(i < target.length() - 1){ 
    			if(j == -1 || target.charAt(j) == target.charAt(i)){ 
    				j++;
    				i++;
    				next[i] = j;
    			}else { 
    				j = next[j];
    			}
    		}
    		return next;
    	}

下面附赠一个方便展示比较过程的辅助类，可以帮助理解。

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class KmpBlog { 
    
    	static class KmpPrint{ 
    		private String src;
    		private String targer;
    		private List<Integer[]> list = new ArrayList();
    		
    		KmpPrint(String src, String target){ 
    			this.src = src;
    			this.targer = target;
    		}
    		
    		public void add(int i1, int i2){ 
    			Integer[] arr = { i1, i2};
    			this.list.add(arr);
    		}
    		
    		public void print(){ 
    			for(Integer[] arr: this.list){ 
    				System.out.println("--------第" + (this.list.indexOf(arr) + 1) + "次比较--------");
    				System.out.println(" " + this.src.charAt(arr[0] + arr[1]) 
    						+ (this.src.charAt(arr[0] + arr[1]) == this.targer.charAt(arr[1]) ? "==" : "!=") 
    						+ this.targer.charAt(arr[1]));
    				System.out.println(this.src);
    				System.out.printf("%" + (this.targer.length() + arr[0]) + "s%n", this.targer);
    			}
    		}
    		
    	}
    	
    	/** * @param args */
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		String src = "asdaseM asdaseN";
    		String target = "asdaseN";
    		
    		System.out.println(kmp(src, target));
    	}
    	
    	public static int kmp(String src, String target){ 
    		
    		KmpPrint prt = new KmpPrint(src, target);
    		
    		int[] next = getNext(target);
    		System.out.println("next : " + Arrays.toString(next));
    			
    		int i = 0;	//src下标
    		int j = 0;	//target下标
    		
    		for(; j < target.length() && i < src.length(); ){ 
    			if(j != -1)
    				prt.add(i - j, j);
    			if(j == -1 || src.charAt(i) == target.charAt(j)){ 
    				i++;
    				j++;
    			}else { 
    				j = next[j];
    			}
    		}
    		
    		if(j == target.length()){ 
    			prt.print();
    			return i - j;
    		}
    			
    		prt.print();
    		return -1;
    	}
    
    	public static int[] getNext(String target){ 
    		int[] next = new int[target.length()];
    		next[0] = -1;
    		int i = 1;
    		int j = 0;
    		
    		while(i < target.length() - 1){ 
    			if(j == -1 || target.charAt(j) == target.charAt(i)){ 
    				j++;
    				i++;
    				next[i] = j;
    			}else { 
    				j = next[j];
    			}
    		}
    		return next;
    	}
    
    }

### kmp算法优化 ###

kmp算法依然存在缺陷。尝试对下面的字符串进行匹配，它的匹配过程应该是这样的

aaaac aaaaac
    aaaaac
    
    --------第1次比较--------
              a==a
    aaaac aaaaac
    aaaaac
    --------第2次比较--------
              a==a
    aaaac aaaaac
    aaaaac
    --------第3次比较--------
              a==a
    aaaac aaaaac
    aaaaac
    --------第4次比较--------
              a==a
    aaaac aaaaac
    aaaaac
    --------第5次比较--------
              c!=a
    aaaac aaaaac
    aaaaac
    --------第6次比较--------
              c!=a
    aaaac aaaaac
     aaaaac
    --------第7次比较--------
              c!=a
    aaaac aaaaac
      aaaaac
    --------第8次比较--------
              c!=a
    aaaac aaaaac
       aaaaac
    --------第9次比较--------
              c!=a
    aaaac aaaaac
        aaaaac
    ...
    ...

可以发现，其中的第6次到第9次比较都是多余的。它们都对a与c进行了比较，但其实，在第6次比较失败后，接下来3次比较的结果已经是可以预测的了。

让我们换一个更加容易理解的短字符串来分析一下。  
`abab` 。按照之前的结论，它对应的next数组应该是`[-1, 0, 0, 1]` 。其中，第4位的1代表的含义也可以这样解释：如果第4位匹配失败，则下一次对第2位（就是上面的结论，3 - 1 = 2）的字符进行匹配。但是，在这个字符串中，第4位与第2位都是b。如果第4位匹配失败，那么第2位也一定会失败，这会产生一次多余的比较。

要优化这个问题也是非常简单。只需要在next数组求解的过程中，若发现当前位（简称位A）与当前位匹配失败后下一次匹配的位（简称位B）相等，则当前位的next值要替换为位B的值。

优化后的next数组求解代码

public static int[] getNext_new(String target){ 
    		int[] next = new int[target.length()];
    		next[0] = -1;
    		int i = 1;
    		int j = 0;
    		
    		while(i < target.length() - 1){ 
    			if(j == -1 || target.charAt(j) == target.charAt(i)){ 
    				j++;
    				i++;
    				//新加的判断
    				if(target.charAt(j) != target.charAt(i)){ 
    					next[i] = j;
    				}else { 
    					next[i] = next[j];
    				}
    				
    			}else { 
    				j = next[j];
    			}
    		}
    		return next;
    	}

这样，字符串`abab` 的next数组就从`[-1, 0, 0, 1]` 变为 `[-1, 0, -1, 0]` 。其他代码与之前一样。