判斷兩個串之間是否存在主串與子串的關(guān)系嘱支，這個過程稱為串的模式匹配蚓胸。
- 在串的模式匹配過程，子串 T 通常被叫做“模式串”除师。
普通的模式匹配（“BF”算法）
判斷兩個串是否存在子串與主串的關(guān)系沛膳，最直接的算法就是拿著模式串，去和主串從頭到尾一一比對汛聚，這就是“BF”算法的實現(xiàn)思想锹安。
將提供的模式串（例如 “abcac” ）從主串的第一個字符開始，依次判斷相同位置的字符是否相等，如果全部相等叹哭，則匹配成功忍宋；反之，將子串向后移動一個字符的位置风罩，繼續(xù)與主串中對應(yīng)的字符匹配糠排。
算法運行過程：（圖中，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;
}
//運行到此继谚，為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”,每次匹配時济瓢，直到匹配最后一個元素，才得知匹配失敗妹卿，運行了 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];
}
}
}
