怎么在java項目中實現一個KMP算法

怎么在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)的效率相對來說就會非常高。

關于怎么在java項目中實現一個KMP算法問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。