花了兩天研究KMP算法，這里做個(gè)簡(jiǎn)單介紹

時(shí)間上由暴力法的O(MN)改良成 O(M+N),所以效率還是可以的封断；其主要思路分為兩步：

1.先處理匹配字符串pattern，生成跳躍數(shù)組next；

2.根據(jù)next數(shù)組記錄括尸，對(duì)待匹配文本進(jìn)行匹配運(yùn)算诫给。

假如有待匹配字符串text：ABABABCDABXYBXYABXYXYZHABCDABXYKEISKAIABAB

有匹配字符串pattern：ABCDABXY

a.先生成next數(shù)組：

| A | B | C | D | A | B | X | Y |
| -1 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |

解釋如下：依次找到pattern字符串中每個(gè)字符的前綴 跟 pattern從頭開(kāi)始的字符串中 重復(fù) 的最大字符個(gè)數(shù)（一定要包含頭香拉，若頭不匹配，就算中間全部匹配也不算）（不包括自身）中狂，例如：pattern字符串從左到右遍歷凫碌，A無(wú)前綴，因此為-1胃榕；B前綴為A盛险，前面從頭開(kāi)始再無(wú)重復(fù)（A不跟自己A比較），因此為0勋又；類似C無(wú)最大重復(fù)前綴苦掘，因此為0；依次類推D楔壤、A前綴為0鹤啡；B最大重復(fù)前綴為A，因此為1蹲嚣；X最大重復(fù)前綴為AB递瑰，因此為2；Y無(wú)最大重復(fù)前綴為隙畜，因此為0.

數(shù)組代表：假如text匹配在X位置錯(cuò)誤抖部，則直接將pattern的X位置換成next[2]對(duì)應(yīng)的C位置，即向前跳躍4個(gè)位置议惰，繼續(xù)一一比較慎颗，依次類推，若pattern長(zhǎng)度匹配到了結(jié)束位置還沒(méi)有跳，則匹配成功一次哗总。若循環(huán)匹配几颜，則成功一次之后還要判斷text該跳躍的長(zhǎng)度，繼續(xù)匹配讯屈；

代碼如下：

    /**
     * 處理pattern蛋哭，記錄跳躍位置數(shù)組
     * @param pattern
     * @return
     */
    public int[] buildNext2(char[] pattern) {
        int k = -1, i = 1, nLen = 0;
        if (pattern == null) {
            return null;
        }
        nLen = pattern.length;
        int next[] = new int[nLen+1];
        next[0] = k;
        for (i = 0; i < nLen; i++) {
            next[i + 1] = next[i] + 1;
            while (next[i + 1] > 0 && pattern[next[i + 1] - 1] != pattern[i]){
                next[i + 1] = next[next[i + 1] - 1] + 1;
            }
        }
        int nnext[] = new int[nLen];
        //此處生成的next數(shù)組會(huì)比原pattern多一位，但不影響比較
//      for(i = 0; i < nLen-1; i++){
//          nnext[i] = next[i];
//      }
//      return nnext;
        return next;

    }

image.gif

<span style="white-space:pre">  </span>/**
     * 匹配算法
     * @param text
     * @param pattern
     * @param next
     */
    public void kmp(char []text, char []pattern, int []next) {
        int i,j,m = 0;
        boolean match = false;

        if (text == null || pattern == null || next == null){
               return;
        }

        //記錄匹配后繼續(xù)匹配文本該跳的位置
        for(i = 0;i<next.length;i++){
            if(next[i]>0){
                m=i-1;
                break;
            }
        }

        for (i=j=0; i != text.length; ) {           //比較結(jié)束符
            if (j<0 || text[i] == pattern[j]) {     //一個(gè)一個(gè)比較
                ++i;
                ++j;
                if (j == pattern.length) {          // 找到了
                    System.out.println("在 "+(i-j)+" 的位置");
                    i=(m==0?i-j+1:i-j+m);           //匹配一次后涮母，文本往后跳一個(gè)next數(shù)組不為0的位置
                j=0;                                //匹配一次后谆趾，pattern回到首位
                    match = true;                   //記錄是否有匹配
                }
            }else{
                j = next[j];
            }
        }
        if(!match){
             System.out.println("沒(méi)有匹配");
        }
    }

image.gif