算法-常用10種算法004-KMP算法

KMP 算法

應用場景-字元串比對問題

字元串比對問題:

1. 有一個字元串 str1=“BBCABCDABABCDABCDABDE”，和一個子串 str2=“ABCDABD”
2. 現在要判斷 str1 是否含有 str2, 如果存在，就傳回第一次出現的位置, 如果沒有，則傳回-1

暴力比對算法

如果用暴力比對的思路，并假設現在 str1 比對到 i 位置，子串 str2 比對到 j 位置，則有:

1.如果目前字元比對成功(即str1[i]==str2[j]),則i++,j++,繼續比對下一個字元
2.如果比對失敗(即str1[i]!=str2[j]),
    令i=i-(j-1),j=0
    相當于,每次比對失敗時,i回溯,j被重置為0.
3.暴力方法解決的話會有大量的回溯,每一次隻移動一位,若是不比對,移動到下一位緊鄰的判斷,浪費了大量的時間.(不可行).      

代碼:

public class ViolenceMatch {

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    //測試暴力比對算法
    String str1="BBCABCDABABCDABCDABDE";
    String str2="ABCDABD";
    int index = violenceMatch(str1, str2);
    System.out.println("index=" + index);

  }

  // 暴力比對算法實作
  public static int violenceMatch(String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();

    int s1Len = s1.length;
    int s2Len = s2.length;

    int i = 0; // i索引指向s1
    int j = 0; // j索引指向s2
    while (i < s1Len && j < s2Len) {// 保證比對時，不越界

      if(s1[i] == s2[j]) {//比對ok
        i++;
        j++;
      } else { //沒有比對成功
        //如果失配（即str1[i]! = str2[j]），令i = i - (j - 1)，j = 0。
        i = i - (j - 1);
        j = 0;
      }
    }  
    //判斷是否比對成功
    if(j == s2Len) {
      return i - j;
    } else {
      return -1;
    }
  }
}      

KMP 算法介紹

KMP 是一個解決模式串在文本串是否出現過，如果出現過，最早出現的位置的經典算法 KMP 方法算法就利用之前判斷過資訊，通過一個 next 數組，儲存模式串中前後最長公共子序列的長度，每次 回溯時，通過 next 數組找到，前面比對過的位置，省去了大量的計算時間

這個算法由 DonaldKnuth、Vaughan Pratt、JamesH.Morris 三人于 1977 年聯合發表，故取這 3 人的 姓氏命名此算法.

KMP 算法最佳應用-字元串比對問題

1. 有一個字元串 str1=“BBCABCDABABCDABCDABDE”，和一個子str2=“ABCDABD”
2. 現在要判斷 str1 是否含有 str2, 如果存在，就傳回第一次出現的位置, 如果沒有則傳回-1
3. 要求：使用 KMP 算法完成判斷，不能使用簡單的暴力比對算法.

思路分析圖解

舉例來說，有一個字元串 Str1 = “BBC ABCDAB ABCDABCDABDE”，判斷，裡面是否包含另一個字元串 Str2 = “ABCDABD”？

1.首先，用 Str1 的第一個字元和 Str2 的第一個字元去比較，不符合，關鍵詞向後移動一位

\2. 重複第一步， 還是不符合， 再後移

\3. 一直重複， 直到 Str1 有一個字元與 Str2 的第一個字元符合為止

\4. 接着比較字元串和搜尋詞的下一個字元， 還是符合。

5.遇到 Str1 有一個字元與 Str2 對應的字元不符合

6.這時候， 想到的是繼續周遊 Str1 的下一個字元， 重複第 1 步。 (其實是很不明智的， 因為此時 BCD 已經比較過了，沒有必要再做重複的工作， 一個基本事實是， 空格與 D 不比對時， 你其實知道前面六個字元是” ABCDAB” 。KMP 算法的想法是， 設法利用這個已知資訊， 不要把” 搜尋位置” 移回已經比較過的位置， 繼續把它向後移，這樣就提高了效率。 )

8.已知空格與 D 不比對時， 前面六個字元” ABCDAB” 是比對的。 查表可知， 最後一個比對字元 B 對應的” 部分比對值” 為 2， 是以按照下面的公式算出向後移動的位數：移動位數 = 已比對的字元數 - 對應的部分比對值因為 6 - 2 等于 4， 是以将搜尋詞向後移動 4 位。

9.因為空格與Ｃ 不比對， 搜尋詞還要繼續往後移。 這時， 已比對的字元數為 2（” AB” ） ， 對應的” 部分比對值”為 0。 是以， 移動位數 = 2 - 0， 結果為 2， 于是将搜尋詞向後移 2 位。

10.因為空格與 A 不比對， 繼續後移一位。

11.逐位比較， 直到發現 C 與 D 不比對。 于是， 移動位數 = 6 - 2， 繼續将搜尋詞向後移動 4 位。

12.逐位比較， 直到搜尋詞的最後一位， 發現完全比對， 于是搜尋完成。 如果還要繼續搜尋（即找出全部比對） ，移動位數 = 7 - 0， 再将搜尋詞向後移動 7 位， 這裡就不再重複了。

13.介紹《部分比對表》 怎麼産生的先介紹字首， 字尾是什麼

“部分比對值” 就是” 字首” 和” 字尾” 的最長的共有元素的長度。 以” ABCDABD” 為例，

－” A” 的字首和字尾都為空集， 共有元素的長度為 0；

－” AB” 的字首為[A]， 字尾為[B]， 共有元素的長度為 0；

－” ABC” 的字首為[A, AB]， 字尾為[BC, C]， 共有元素的長度 0；

－” ABCD” 的字首為[A, AB, ABC]， 字尾為[BCD, CD, D]， 共有元素的長度為 0；

－” ABCDA” 的字首為[A, AB, ABC, ABCD]， 字尾為[BCDA, CDA, DA, A]， 共有元素為” A” ， 長度為 1；

－” ABCDAB” 的字首為[A, AB, ABC, ABCD, ABCDA]， 字尾為[BCDAB, CDAB, DAB,AB, B]， 共有元素為” AB”，長度為 2；

－” ABCDABD” 的字首為[A, AB, ABC, ABCD, ABCDA, ABCDAB]， 字尾為[BCDABD,CDABD, DABD, ABD, BD,D]， 共有元素的長度為 0。

14.” 部分比對” 的實質是， 有時候， 字元串頭部和尾部會有重複。 比如， ” ABCDAB” 之中有兩個” AB” ， 那麼它的” 部分比對值” 就是 2（” AB” 的長度） 。 搜尋詞移動的時候， 第一個” AB” 向後移動 4 位（字元串長度-部分比對值） ， 就可以來到第二個” AB” 的位置。

代碼核心部位:

//KMP算法核心點, 可以驗證...
            while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j-1]; 
            }
 //這時kmp算法的核心點
    while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
     j = next[j-1];
     }          
      

public static  int[] kmpNext(String dest) {
    //建立一個next 數組儲存部分比對值
    int[] next = new int[dest.length()];
    next[0] = 0; //如果字元串是長度為1 部分比對值就是0
    for(int i = 1, j = 0; i < dest.length(); i++) {
      //當dest.charAt(i) != dest.charAt(j) ，我們需要從next[j-1]擷取新的j
      //直到我們發現 有  dest.charAt(i) == dest.charAt(j)成立才退出
      //這時kmp算法的核心點
      while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
        j = next[j-1];
      }
      
      //當dest.charAt(i) == dest.charAt(j) 滿足時，部分比對值就是+1
      if(dest.charAt(i) == dest.charAt(j)) {
        j++;
      }
      next[i] = j;
    }
    return next;
  }      

完整代碼

package com.atguigu.kmp;

import java.util.Arrays;

public class KMPAlgorithm {

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    String str1 = "BBC ABCDAB ABCDABCDABDE";
    String str2 = "ABCDABD";
    //String str2 = "BBC";
    
    int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
    System.out.println("next=" + Arrays.toString(next));
    
    int index = kmpSearch(str1, str2, next);
    System.out.println("index=" + index); // 15了
    
    
  }
  
  //寫出我們的kmp搜尋算法
  /**
   * 
   * @param str1 源字元串
   * @param str2 子串
   * @param next 部分比對表, 是子串對應的部分比對表
   * @return 如果是-1就是沒有比對到，否則傳回第一個比對的位置
   */
  public static int kmpSearch(String str1, String str2, int[] next) {
    
    //周遊 
    for(int i = 0, j = 0; i < str1.length(); i++) {
      
      //需要處理 str1.charAt(i) ！= str2.charAt(j), 去調整j的大小
      //KMP算法核心點, 可以驗證...
      while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
        j = next[j-1]; 
      }
      
      if(str1.charAt(i) == str2.charAt(j)) {
        j++;
      }      
      if(j == str2.length()) {//找到了 // j = 3 i 
        return i - j + 1;
      }
    }
    
    return  -1;
  }

  //擷取到一個字元串(子串) 的部分比對值表
  public static  int[] kmpNext(String dest) {
    //建立一個next 數組儲存部分比對值
    int[] next = new int[dest.length()];
    next[0] = 0; //如果字元串是長度為1 部分比對值就是0
    for(int i = 1, j = 0; i < dest.length(); i++) {
      //當dest.charAt(i) != dest.charAt(j) ，我們需要從next[j-1]擷取新的j
      //直到我們發現 有  dest.charAt(i) == dest.charAt(j)成立才退出
      //這時kmp算法的核心點
      while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
        j = next[j-1];
      }
      
      //當dest.charAt(i) == dest.charAt(j) 滿足時，部分比對值就是+1
      if(dest.charAt(i) == dest.charAt(j)) {
        j++;
      }
      next[i] = j;
    }
    return next;
  }
}