問題：有一個文本串S，和一個模式串P，現(xiàn)在要查找P在S中的位置
輸入：“abcdef”，“bc”
"abcdefg" ,"ba"
輸出：1
-1

暴力匹配

并假設(shè)現(xiàn)在文本串S匹配到 i 位置，模式串P匹配到 j 位置，則有：
如果當(dāng)前字符匹配成功（即S[i] == P[j]），則i++，j++，繼續(xù)匹配下一個字符；
如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相當(dāng)于每次匹配失敗時，i 回溯，j 被置為0。

int violent(char *s,char *p){
    int sLen = strlen(s);
    int pLen = strlen(p);
    int i = 0;
    int j = 0;
    while(i<sLen && j<pLen){
        if(s[i] == p[j]){
            i++;
            j++;
        }
        else{
            i = i-j+1;
            j = 0;
        }
    }
    //匹配成功，返回模式串p在文本串s中的位置，否則返回-1
    if (j == pLen)
        return i - j;
    else
        return -1;

}

KMP 算法
下面先直接給出KMP的算法流程（具體教程：<a href= http://blog.csdn.net/v_july_v/article/details/7041827> 詳細(xì)教程傳送門</a>）：
假設(shè)現(xiàn)在文本串S匹配到 i 位置，模式串P匹配到 j 位置
如果j = -1，或者當(dāng)前字符匹配成功（即S[i] == P[j]），都令i++，j++，繼續(xù)匹配下一個字符；
如果j != -1，且當(dāng)前字符匹配失敗（即S[i] != P[j]），則令 i 不變，j = next[j]。此舉意味著失配時，模式串P相對于文本串S向右移動了j - next [j] 位。
換言之，當(dāng)匹配失敗時，模式串向右移動的位數(shù)為：失配字符所在位置 - 失配字符對應(yīng)的next 值，即移動的實際位數(shù)為：j - next[j]，且此值大于等于1。（實際上相當(dāng)于當(dāng)前位和next[j]位比）

void GetNext(char* p,int next[])
{
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
        //p[k]表示前綴，p[j]表示后綴
        if (k == -1 || p[j] == p[k])
        {
            ++k;
            ++j;
            if (p[j] != p[k])
                next[j] = k;   //之前只有這一行
            else
                //因為不能出現(xiàn)p[j] = p[ next[j ]]，所以當(dāng)出現(xiàn)時需要繼續(xù)遞歸，k = next[k] = next[next[k]]
                next[j] = next[k];
        }
        else
        {
            k = next[k];
        }
    }
}
int kmp(char *s,char *p){
    int sLen = strlen(s);
    int pLen = strlen(p);
    int next[pLen];
    GetNext(p,next);
    int i = 0;
    int j = 0;
    
    while(i<sLen && j<pLen){
        if(j == -1 || s[i] == p[j]){
            i++;
            j++;
            
        }
        else{
            j = next[j];
        }
    }
    //匹配成功，返回模式串p在文本串s中的位置，否則返回-1
    if (j == pLen)
        return i - j;
    else
        return -1;
    
}

時間復(fù)雜度
我們發(fā)現(xiàn)如果某個字符匹配成功，模式串首字符的位置保持不動，僅僅是i++、j++；如果匹配失配，i 不變（即 i 不回溯），模式串會跳過匹配過的next [j]個字符。整個算法最壞的情況是，當(dāng)模式串首字符位于i - j的位置時才匹配成功，算法結(jié)束。 所以，如果文本串的長度為n，模式串的長度為m，那么匹配過程的時間復(fù)雜度為O(n)，算上計算next的O(m)時間，KMP的整體時間復(fù)雜度為O(m + n)。

Reference：
<a >從頭到尾徹底理解KMP</a>