怎么在java項(xiàng)目中實(shí)現(xiàn)一個(gè)KMP算法？針對這個(gè)問題，這篇文章詳細(xì)介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問題的小伙伴找到更簡單易行的方法。

成都創(chuàng)新互聯(lián)公司是一家專業(yè)提供北關(guān)企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站建設(shè)、H5建站、小程序制作等業(yè)務(wù)。10年已為北關(guān)眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站制作公司優(yōu)惠進(jìn)行中。

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

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

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

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

以上面gif圖中的兩個(gè)字符串

txt = “aaacaaab”

pat = “aaab”

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

簡單原理：構(gòu)建狀態(tài)轉(zhuǎn)移數(shù)組，當(dāng)遇到無法匹配的字符時(shí)根據(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ù)組是一個(gè)Int類型的狀態(tài)碼數(shù)組，每個(gè)元素的含義是回溯時(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; // 保存的同時(shí)移步下一位
      }else {
        // 如果 i 和 j 指向的字符不相同，則保持i不動(dòng)，回溯j
        // 如果回溯后的j指向的字符與i相同，則將此時(shí)的狀態(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)入下一個(gè)狀態(tài)
      }
      if (j == pattern.length()-1){ // 如果成功匹配，返回true
        return true;
      }
    }
    return false;// 匹配不成功
  }
}

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

在對比較短的目標(biāo)字符串而言，毫無疑問使用暴力法的效率（時(shí)間復(fù)雜度為O（M*N）會(huì)快一點(diǎn)，而當(dāng)目標(biāo)字符串的長度非常長以后，暴力匹配的效率就會(huì)大打折扣。

對于非常長的字符串來說，KMP的O(M+N)的效率相對來說就會(huì)非常高。

關(guān)于怎么在java項(xiàng)目中實(shí)現(xiàn)一個(gè)KMP算法問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識(shí)。

當(dāng)前文章：怎么在java項(xiàng)目中實(shí)現(xiàn)一個(gè)KMP算法-創(chuàng)新互聯(lián)
標(biāo)題URL：http://weahome.cn/article/doiijs.html