java 实现KMP算法

KMP算法是一种神奇的字符串匹配算法，在对 超长字符串 进行模板匹配的时候比暴力匹配法的效率会高不少。接下来我们从思路入手理解KMP算法。

在对字符串进行匹配的时候我们最容易想到的就是一个个匹配，类似下面这种：

换成Java代码就是：

public static boolean bfSearch(String pattern,String txt){
   if (txt.length() < pattern.length())
     return false;
   for (int i = 0; i < txt.length(); i++) {
     boolean flag = false;
     for (int j = 0; j < pattern.length(); j++) {
       if (i+j>=txt.length())
         return false;
       if (txt.charAt(i+j)!=pattern.charAt(j)){
         flag = true;
       }
     }
     if (!flag){
       return true;
     }
   }
   return false;
 }

暴力匹配算法的时间复杂度为O(n*m)，n为模板字符串，m为目标字符串，在处理复杂字符串时毫无疑问效率会非常低，由此诞生了KMP算法（时间复杂度为O(m+n) )。

以上面gif图中的两个字符串

txt = “aaacaaab”

pat = “aaab”

为例我们来说一下KMP算法的思路。个人能力有限，您可以先行观看此视频去简单学习KMP的基本原理。

简单原理：构建状态转移数组，当遇到无法匹配的字符时根据状态转移数组进行回溯，以达到减少遍历次数的目的。

1.首先构建状态转移数组：

对匹配模式字符串进行遍历
从左向右遍历，如果 i 和 j（见源码）所指向的元素相同，则将此状态（j所指向的元素位置）进行保存
最后保存的数组是一个Int类型的状态码数组，每个元素的含义是回溯时模板字符串（pattern）的状态。

2.构建完成后通过状态转移数组和匹配模式字符串对传入的目标字符串进行匹配。过程如下：

对目标字符串进行遍历，检索相同的字符元素。
如果遇到不同的字符元素，根据 J（模板字符串的指针）所在的位置依靠状态转移数组来回溯遍历状态。并在回溯后继续进行匹配。

3.源码如下：

import java.util.Arrays;

public class KMP {
 private int[] patArray; // 状态转移数组
 private final String pattern;// 匹配模式字符串
 public static boolean bfSearch(String pattern,String txt){
   if (txt.length() < pattern.length())return false;
   for (int i = 0; i < txt.length(); i++) {
     boolean flag = false;
     for (int j = 0; j < pattern.length(); j++) {
       if (i+j>=txt.length())return false;
       if (txt.charAt(i+j)!=pattern.charAt(j)){
         flag = true;
       }
     }
     if (!flag){
       return true;
     }
   }
   return false;
 }
 KMP(String pat) { // 通过匹配模式字符串构建对象
   this.pattern = pat;
   patArray = new int[pattern.length()]; // 创建状态转移数组
   int j = 0;
   for (int i = 1; i < pattern.length(); ) {
     if (pattern.charAt(i) == pattern.charAt(j)){
       // 如果i和j指向的字符相同，则将此状态进行保存
       patArray[i++] = ++j; // 保存的同时移步下一位
     }else {
       // 如果 i 和 j 指向的字符不相同，则保持i不动，回溯j
       // 如果回溯后的j指向的字符与i相同，则将此时的状态进行保存
       if (j <= pattern.length() - 1 && j >0) {
         j=patArray[--j]; // 回溯j
         if (pattern.charAt(i) == pattern.charAt(j)) {
           // 如果回溯后相同，则保存状态
           patArray[i++] = ++j;
         }
       }else if (j == 0) {
         // 如果回溯到头，则保存为0状态
         patArray[++i] = 0;
       }
     }
   }
 }
 boolean search(String txt){
   int j = 0;
   for (int i = 0; i < txt.length(); i++) {
     // 对输入的字符串进行模式匹配
     if (txt.charAt(i) != pattern.charAt(j)){
       // 如果匹配不成功，则根据状态数组对j进行状态更改
       if (j>0)--j; // 回溯
       j = patArray[j];
     }else {
       ++j; // 匹配成功则进入下一个状态
     }
     if (j == pattern.length()-1){ // 如果成功匹配，返回true
       return true;
     }
   }
   return false;// 匹配不成功
 }
}

后续的一些思考：

在对比较短的目标字符串而言，毫无疑问使用暴力法的效率（时间复杂度为O（M*N）会快一点，而当目标字符串的长度非常长以后，暴力匹配的效率就会大打折扣。

对于非常长的字符串来说，KMP的O(M+N)的效率相对来说就会非常高。

来源：https://farewell12345.github.io/farewell12345.github.io/2020/09/25/KMP％E7％AE％97％E6％B3％95/?t=1608887980729