在一個字符串（目標串）中查找一個子串（模式串）是否存在，如若查找成功返回子串第一個字符位置，否則查找失敗。

暴力匹配

主串的第i個字符如果與子串第一個字符匹配，則依次比較后邊的字符，如果未完全匹配成功，也就是說后邊有一個字符不一致，下一輪的匹配從主串的第i+1個與子串的第一個重新進行，直到匹配成功，返回下標，否則匹配失敗。
該算法效率很低，每次匹配失敗都要重新匹配，最壞情況下O(n*m)的復(fù)雜度，很多時候不能滿足我們的要求。

      int blfind(String S,String T){
        int i=0,j=0;
        while(i<S.length() && j<T.length()){
            if(S[i]==T[j]){
                i++;
                j++;
            }
            else{
                i=i-j+1; 
                j=0;
            }
        }
        if(j==T.length()  return i-j;
        else  return -1;
    }

KMP模式匹配算法

先前我們是在不匹配的時候返回主串的頭部繼續(xù)匹配，我們可以想辦法優(yōu)化這種做法，當主串 S[i]與T[j]失配，我們不再移動i指針，而是移動j指針。大家想一下s[i]之前匹配成功的部分，是不是和T[0]-T[j-1]是一樣的，如果找出T[0]到T[j-1]的相同前后綴的長度，是不是可以直接將j移動到相同前綴的下一個位置。
ababcababa 主串
ababa子串
我們在匹配到'a'和'c' 不等的時候 子串中abab 前綴ab 和后綴ab是相同的，它的前綴和主串中已經(jīng)匹配的后綴一定是相同的 ，所以j指向子串中ababa的第三個字符‘a(chǎn)’，而i仍然指向c ，再次進行匹配，如若失配，不斷地調(diào)整j指針就可以。
如何解決最長公共前后綴的問題，我們采用的next數(shù)組。

void getNext(){  //求next數(shù)組,這里T是模式串
        next[0]=-1; //因為我們是求0到j(luò)-1的，所以0初始化為-1.
        int j=0,k=-1; 
        while(j<T.length()-1){
            if(k==-1 || T[j]==T[k])
                next[++j]=++k; //next[j]表示 當S[i]和T[j]失配時，j指針的位置
            else
                k=next[k];  //這里非常巧妙，回溯的思想。  next[k]是T[k]之前字符串的最長公共前后綴，
// 而T[next[k]]就是這個最長公共前后綴中前綴的最后一個字符
        }
    }

int KMP() {
    int i = 0;
    int j = 0;
    getNext();
    while (i < S.length() && j < T.length()) {
        if (S[i] == T[j]) {
            i++;
            j++;
        }
     else if(next[j]==-1) i++; 
    else  j = next[j];
    }
    if (j == T.length())
        return i - j;
    else
        return -1;
}

它的時間復(fù)雜度是O(n+m)，很高效，此外，next數(shù)組的思想還可以解決很多字符串中的問題。