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的基本原理。

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

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

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

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)的效率相对来说就会非常高。

以上就是java 实现KMP算法的详细内容，更多关于java 实现KMP算法的资料请关注考高分网其它相关文章！