串的模式匹配

1.樸素的模式匹配（Brute-Force）算法

假設(shè)待匹配的目標(biāo)串是adbcade，而模式串是ade，那么匹配的時候是按:

    a--d--b-->不匹配;
    d-->不匹配;   //注意這里在上一個發(fā)現(xiàn)不匹配時，是從上一個匹配開始的下一個位置開始重新匹配的。

Brute-Force算法的實(shí)現(xiàn)：

public int indexOf(String target,String pattern){
        //判斷目標(biāo)串，匹配串是否滿足條件。
        if(pattern != null && target != null && target.length() >= pattern.length()){
            //start指開始匹配的字符起始位置
            int start = 0;
            //count指匹配到的字符數(shù)目
            int count = 0;
            //當(dāng)目標(biāo)串剩余未匹配的長度大于或等于匹配串串長度，循環(huán)繼續(xù)
            while(target.length() - start >= pattern.length()){
                //滿足條件
                if(target.charAt(count + start) == pattern.charAt(count)){              
                    //匹配一個字符后加一。
                    count ++;
                }else{
                        //不滿足匹配，count置零，起始匹配位置加一。
                    count = 0;
                    start ++;
                }
                //若count==pattern，說明已經(jīng)完成了一次匹配。
                if(count == pattern.length()){
                    return start;
                }
            }
        }
        //匹配失敗返回-1
        return -1;
    }

測試程序以及運(yùn)行結(jié)果：

public static void main(String[] args) {
        // TODO Auto-generated method stub
        String target = "adbcade";
        String pattern = "ade";
        BruteForceStringPattern sfsp = new BruteForceStringPattern();
        System.out.println(sfsp.indexOf(target, pattern));
    }
    
    4

Brute-Force算法易于理解，但是時間效率不高。它是一種帶回溯的模式匹配算法，將目標(biāo)串中所有長度為匹配串長度的字串依次與匹配串比較。

雖然沒有任何丟失可能匹配字符的可能，但是每次的匹配沒有用到前一次匹配的比較結(jié)果，比較多次重復(fù)，降低了算法效率。
時間復(fù)雜度：
m = pattern.length();
n = target.length();
最好的情況：O(m) (一次比較成功)
最壞的情況：O(n(n-m+1)m) 一般n>>m，所以O(shè)(nm) (比較到最后一次才成功）

2.無回溯的模式匹配（KMP）算法

先來一波kmp算法的百科介紹：

KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)
，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP算法）。
KMP算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。
具體實(shí)現(xiàn)就是實(shí)現(xiàn)一個next()函數(shù)，函數(shù)本身包含了模式串的局部匹配信息。

無回溯的模式匹配算法首先目標(biāo)串的祛除了目標(biāo)串的回溯，其次，通過getNext()算法，匹配串也做到了部分不回溯。

無回溯算法的核心是如何實(shí)現(xiàn)這個next（）算法：

    public int[] next(String pattern){
        int i = -1;
        int j = 0;
        int[] next = new int[pattern.length()];
        next[0] = -1;
        while(j < pattern.length() - 1){
            if(i == -1 || pattern.charAt(i) == pattern.charAt(j)){
                i++;
                j++;
                next[j] = i;
            }else{
                i = -1;
            }
        }
        return next;
    }

實(shí)際上next()算法就是來 判斷pattern的子字符串與當(dāng)pattern的0位置開始的字符串是否相同，第一個next[0]默認(rèn)為1，接下來的如果不相同next[i]為0，如果第一個相同，為0,若連續(xù)開始相同，則依次++1
如:

aaaaaaa的next():
[-1,0,1,2,3,4,5]

abab的next():
[-1,0,0,1]

如果pattern的首字符在pattern剩余的字符串里沒有再出現(xiàn)過，那么getNext()獲取的next[]必然是[-1,0,...,0]這樣的。

匹配方法如下：

public int kmp(String target,String pattern){
        if(target != null && pattern != null && target.length() > pattern.length()){
            int start = 0;
            int[] next = next(pattern);
            int count = next[start];
            while(target.length() - start + count >= pattern.length()){
                if(count == -1 || target.charAt(start) == pattern.charAt(count)){
                    count ++;
                    start ++;
                }else{
                    //這里就是核心了，如果next[count] <= 0 目標(biāo)字符串直接從當(dāng)前的下一個開始比較。
                    //因?yàn)榈扔?1的話說明是在匹配第一個字符串，當(dāng)前匹配失敗，不可能再與pattern第一個字符匹配了，當(dāng)然是要繼續(xù)匹配下一個，如果是0的話，說明是在匹配第一個與pattern頭相同的串或者匹配與pattern頭無關(guān)的字符，匹配失敗，當(dāng)然也是繼續(xù)匹配下一個字符串。
                    count = next[count];
                }
                
                if(count == pattern.length()){
                    return start - count;
                }
            }
        }
        return -1;
    }

kmp算法的最壞的比較次數(shù)是m+n，next算法的時間復(fù)雜度是0(m),kmp比較是O(n)，與BF算法相比，已經(jīng)大大縮小了比較的時間。