快捷導(dǎo)航

java 實(shí)現(xiàn)KMP算法

更新時間：2020年12月25日 17:26:52 作者：傘菌

這篇文章主要介紹了java 如何實(shí)現(xiàn)KMP算法，幫助大家更好的理解和學(xué)習(xí)Java，感興趣的朋友可以了解下

KMP算法是一種神奇的字符串匹配算法，在對超長字符串進(jìn)行模板匹配的時候比暴力匹配法的效率會高不少。接下來我們從思路入手理解KMP算法。

在對字符串進(jìn)行匹配的時候我們最容易想到的就是一個個匹配，類似下面這種：

換成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;
  }

暴力匹配算法的時間復(fù)雜度為O(n*m)，n為模板字符串，m為目標(biāo)字符串，在處理復(fù)雜字符串時毫無疑問效率會非常低，由此誕生了KMP算法（時間復(fù)雜度為O(m+n) )。

以上面gif圖中的兩個字符串

txt = “aaacaaab”

pat = “aaab”

為例我們來說一下KMP算法的思路。個人能力有限，您可以先行觀看此視頻去簡單學(xué)習(xí)KMP的基本原理。

簡單原理：構(gòu)建狀態(tài)轉(zhuǎn)移數(shù)組，當(dāng)遇到無法匹配的字符時根據(jù)狀態(tài)轉(zhuǎn)移數(shù)組進(jìn)行回溯，以達(dá)到減少遍歷次數(shù)的目的。

1.首先構(gòu)建狀態(tài)轉(zhuǎn)移數(shù)組：

對匹配模式字符串進(jìn)行遍歷
從左向右遍歷，如果 i 和 j（見源碼）所指向的元素相同，則將此狀態(tài)（j所指向的元素位置）進(jìn)行保存
最后保存的數(shù)組是一個Int類型的狀態(tài)碼數(shù)組，每個元素的含義是回溯時模板字符串（pattern）的狀態(tài)。

2.構(gòu)建完成后通過狀態(tài)轉(zhuǎn)移數(shù)組和匹配模式字符串對傳入的目標(biāo)字符串進(jìn)行匹配。過程如下：

對目標(biāo)字符串進(jìn)行遍歷，檢索相同的字符元素。
如果遇到不同的字符元素，根據(jù) J（模板字符串的指針）所在的位置依靠狀態(tài)轉(zhuǎn)移數(shù)組來回溯遍歷狀態(tài)。并在回溯后繼續(xù)進(jìn)行匹配。

3.源碼如下：

import java.util.Arrays;

public class KMP {
  private int[] patArray; // 狀態(tài)轉(zhuǎn)移數(shù)組
  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) { // 通過匹配模式字符串構(gòu)建對象
    this.pattern = pat;
    patArray = new int[pattern.length()]; // 創(chuàng)建狀態(tài)轉(zhuǎn)移數(shù)組
    int j = 0;
    for (int i = 1; i < pattern.length(); ) {
      if (pattern.charAt(i) == pattern.charAt(j)){ 
        // 如果i和j指向的字符相同，則將此狀態(tài)進(jìn)行保存
        patArray[i++] = ++j; // 保存的同時移步下一位
      }else {
        // 如果 i 和 j 指向的字符不相同，則保持i不動，回溯j
        // 如果回溯后的j指向的字符與i相同，則將此時的狀態(tài)進(jìn)行保存
        if (j <= pattern.length() - 1 && j >0) {
          j=patArray[--j]; // 回溯j
          if (pattern.charAt(i) == pattern.charAt(j)) { 
            // 如果回溯后相同，則保存狀態(tài)
            patArray[i++] = ++j;
          }
        }else if (j == 0) { 
          // 如果回溯到頭，則保存為0狀態(tài)
          patArray[++i] = 0;
        }
      }
    }
  }
  boolean search(String txt){
    int j = 0;
    for (int i = 0; i < txt.length(); i++) { 
      // 對輸入的字符串進(jìn)行模式匹配
      if (txt.charAt(i) != pattern.charAt(j)){
        // 如果匹配不成功，則根據(jù)狀態(tài)數(shù)組對j進(jìn)行狀態(tài)更改
        if (j>0)--j; // 回溯
        j = patArray[j];
      }else {
        ++j; // 匹配成功則進(jìn)入下一個狀態(tài)
      }
      if (j == pattern.length()-1){ // 如果成功匹配，返回true
        return true;
      }
    }
    return false;// 匹配不成功
  }
}

后續(xù)的一些思考：