JAVA實現(xiàn)KMP算法理論和示例代碼

更新時間：2013年11月14日 11:49:49 作者：

本文從理論到代碼講解了JAVA對KMP算法的實現(xiàn)，大家可以參考一下

一.理論準備
KMP算法為什么比傳統(tǒng)的字符串匹配算法快？KMP算法是通過分析模式串，預先計算每個位置發(fā)生不匹配的時候，可以省去重新匹配的的字符個數(shù)。整理出來發(fā)到一個next數(shù)組，然后進行比較，這樣可以避免字串的回溯，模式串中部分結果還可以復用，減少了循環(huán)次數(shù)，提高匹配效率。通俗的說就是KMP算法主要利用模式串某些字符與模式串開頭位置的字符一樣避免這些位置的重復比較的。例如主串： abcabcabcabed ,模式串：abcabed。當比較到模式串'e'字符時不同的時候完全沒有必要從模式串開始位置開始比較直接從模式串的'c'字符開始比較就可以了。并且主串也不用回溯了。
傳統(tǒng)的匹配算法沒有利用匹配過的信息(模式串是知道的，那么部分匹配主串也是知道的)，每次都從頭開始比較，速度很慢。
先介紹前綴數(shù)組(我自己這么叫的，不知道對不對)是如何產(chǎn)生的。首先，要了解兩個概念："前綴"和"后綴"。 "前綴"指除了最后一個字符以外，一個字符串的全部頭部組合；"后綴"指除了第一個字符以外，一個字符串的全部尾部組合。
來看一個例子：chi表示模式串的前i個字符組成的前綴， next[i] = j表示chi中的開始j個字符和末尾j個字符是一樣的(注意下標是字符數(shù)目)，而且對于前綴chi來說，這樣的j是最大值。next[i] = j的另外一個定義是：有一個含有j個字符的串，它既是chi的真前綴，又是chi的真后綴。
規(guī)定：next[1] = next[0] = 0，這個規(guī)定不像0！=1那樣，而是確實是這樣子，不懂得看上面的前后綴概念。注意：next數(shù)組里并不是首尾回文串，而是前綴等于后綴，理解這個對于遞推求next數(shù)組很重要喲。next[i]就是前綴數(shù)組，下面通過1個例子來看如何構造前綴數(shù)組。
例：cacca有5個前綴，求出其對應的next數(shù)組。前綴2為ca，顯然首尾沒有相同的字符，next[2] = 0，前綴3為cac，顯然首尾有共同的字符c，故next[3] = 1，前綴4為cacc，首尾有共同的字符c，故next[4] = 1，前綴5為cacca，首尾有共同的字符ca，故next[5] = 2。如果仔細觀察，可以發(fā)現(xiàn)構造next[i]的時候，可以利用next[i-1]的結果。比如abcdabc，模式已求得next[7] = 3，為求next[8]，可以直接比較第4個字符和第8個字符，如果它們相等，則next[8] = next[7]+1 = 4，這是因為next[7] = 3保證了前綴ch7的末尾4個字符的前3個字符是一樣的。但如果這兩個字符不想等呢？那就繼續(xù)迭代，利用(k=3)k = next[k]的值來求,直到k=0(next[8] = 0)或者字符相等(next[8] = k+1)。
二.算法實現(xiàn)

復制代碼代碼如下:

import java.util.ArrayList;
public class KMP {
 //主串
 static String str = "1kk23789456789hahha";
 //模式串
 static String ch = "789";
 static int next[] = new int[20];

 public static void main(String[] args) {
  setNext();
  ArrayList<Integer> arr = getKmp();
  if(arr.size()!=0) {
   for(int i=0; i<arr.size(); i++) {
    System.out.println("匹配發(fā)生在:"+arr.get(i));
   }
  }else {
   System.out.println("匹配不成功");
  }
 }
 private static void setNext() {
  // TODO Auto-generated method stub
  int lenCh = ch.length();
  next[0] = 0;
  next[1] = 1;
  //k表示next[i-1]的值
  int k = 0;
  for(int i=2; i<=lenCh; i++) {
   k = next[k];
   /*
    * 這個while循環(huán)的作用找個例子看看就好理解了
    * 我認為是每次找最長，一旦成功就停止，保證找到的是當前最長
    */
   while(k!=0 && ch.charAt(i-1)!=ch.charAt(k)) {
    k = next[k];
   }
   if(ch.charAt(i-1)==ch.charAt(k)) {
    k++;
   }//else就是k=0
   //不是next[k] = k，i表示有幾個字符的前綴
   next[i] = k;
  }
 }
 private static ArrayList<Integer> getKmp() {
  // TODO Auto-generated method stub
  ArrayList<Integer> arr = new ArrayList<Integer>();
  int lenStr = str.length();
  int lenCh = ch.length();
  //主串開始的匹配位置
  int pos = 0;
  //模式串每次匹配位置
  int k = 0;
  //循環(huán)條件不是k<lenCh,這樣的話可能死循環(huán)(沒有匹配發(fā)生)
  while(pos<lenStr) {
   /*
    * 首次進入沒什么大作用，做要是為提高以后的匹配效率
    * 寫在最后一行也行
    */
   k = next[k];
   while(k<lenCh && str.charAt(pos)==ch.charAt(k)) {
    pos++;
    k++;
   }
   if(lenCh==k) {
    arr.add(pos-k);
   }else if(0==k) {
    /*
     * 不加這一句死循環(huán)
     * 因為next[0] = 0
     * 比如abcd和abce，到de不匹配，此時執(zhí)行k = next[k](k=3),
     * k變?yōu)?，發(fā)現(xiàn)d和a不匹配，此時k還是0，重復執(zhí)行以上步驟，那么死循環(huán)了
     */
    pos++;
   }//實際上else就是k = next[k]，所以才說k = next[k]寫在最后一行也行
  }
  return arr;
 }

}

三.問題擴展
KMP算法的高效性往往是在模式串比較長的時候才能體現(xiàn)出來(看next數(shù)組的推導過程)，而實際上模式串往往很短，回想自己使用辦公套件時查找的字符串長度，所以實踐上大多使用BM算法來實現(xiàn)，感興趣的讀者可以自己查閱相關資料，或許可以再看看多模匹配(在主串中一次查找多個模式串)的AC自動機、dictmatch算法。

您可能感興趣的文章: