判斷兩個串之間是否存在主串與子串的關(guān)系，這個過程稱為串的模式匹配。

• 在串的模式匹配過程，子串 T 通常被叫做“模式串”。

普通的模式匹配（“BF”算法）

判斷兩個串是否存在子串與主串的關(guān)系，最直接的算法就是拿著模式串，去和主串從頭到尾一一比對，這就是“BF”算法的實現(xiàn)思想。

將提供的模式串（例如 “abcac” ）從主串的第一個字符開始，依次判斷相同位置的字符是否相等，如果全部相等，則匹配成功；反之，將子串向后移動一個字符的位置，繼續(xù)與主串中對應(yīng)的字符匹配。

算法運(yùn)行過程：（圖中，i 和 j 表示匹配字符在數(shù)組中的位置下標(biāo)）

如圖所示，第一次匹配，模式串和主串匹配到第三個字符時，匹配失敗；模式串向右移動一個字符的位置，還是從第一個字符 ‘a(chǎn)’ 和主串的第二個字符 ‘b’ 相匹配，匹配失??；模式串繼續(xù)后移一個字符的位置，繼續(xù)匹配。

#include <stdio.h>
#include <string.h>
int sel(char * S,char *T){
    int i=0,j=0;
    while (i<strlen(S) && j<strlen(T)) {
        if (S[i]==T[j]) {
            i++;
            j++;
        }else{
            i=i-j+1;
            j=0;
        }
    }
    //跳出循環(huán)有兩種可能，i=strlen(S)說明已經(jīng)遍歷完主串；j=strlen(T),說明模式串遍歷完成，在主串中成功匹配
    if (j==strlen(T)) {
        return i-strlen(T)+1;
    }
    //運(yùn)行到此，為i==strlen(S)的情況
    return 0;
}
int main() {
    int add=sel("ababcabcacbab", "abcac");
    printf("%d",add);
    return 0;
}

時間復(fù)雜度

“BF” 算法在最理想的情況下的時間復(fù)雜度為O(m)( m 是模式串的長度，也就是第一次匹配就成功的情況)。

一般情況下，"BF"算法的時間復(fù)雜度為O(n+m)(n是主串的長度，m是模式串的長度)。

最壞的情況下的時間復(fù)雜度為O(nm)（例如主串 S 為“000000000001”，模式串 T ”001”,每次匹配時，直到匹配最后一個元素，才得知匹配失敗，運(yùn)行了 nm 次）。

KMP算法

串的普通模式匹配算法，大體思路是：模式串從主串的第一個字符開始匹配，每匹配失敗，主串中記錄匹配進(jìn)度的指針 i 都要進(jìn)行 i-j+1 的回退操作（這個過程稱為“指針回溯”），同時模式串向后移動一個字符的位置。一次次的循環(huán)，直到匹配成功或者程序結(jié)束。

"KMP"算法相比于"BF"算法，優(yōu)勢在于：
在保證指針 i 不回溯的前提下，當(dāng)匹配失敗時，讓模式串向右移動最大的距離；
并且可以在O(n+m)的時間數(shù)量級上完成對串的模式匹配操作；

故，"KMP"算法稱為“快速模式匹配算法”。

next函數(shù)實現(xiàn)

#include <stdio.h>
#include <string.h>
void Next(char*T,int *next){
    int i=1;
    next[0]=0;
    int j=0;
    while (i<strlen(T)) {
        if (j==0||T[i-1]==T[j-1]) {
            i++;
            j++;
            next[i]=j;
        }else{
            j=next[j];
        }
    }
}