在對(duì)字符串的操作中，我們經(jīng)常要用到子串的查找功能，我們稱子串為模式串，模式串在主串中的查找過程我們成為模式匹配，KMP算法就是一個(gè)高效的模式匹配算法。KMP算法是蠻力算法的一種改進(jìn)，下面我們先來介紹蠻力算法。
蠻力算法使用兩個(gè)int型變量當(dāng)做當(dāng)前匹配位置的指針，我們假設(shè)主串的位置指針為i，模式串的位置指針為j。蠻力算法的策略便是在i和j所指的位置的字符相等時(shí)，繼續(xù)向后匹配，當(dāng)發(fā)生失配時(shí)，便將i回溯到本次匹配前位置的后一個(gè)位置，而將j設(shè)置為0，從而對(duì)所有位置完成逐一比對(duì)，通過觀察i和j是否越界判斷整體匹配是否成功，若模式串位置指針j越界，顯然此前所有位置都已完全匹配，那么也就可以返回i-j也即完全匹配時(shí)主串中匹配子串的下標(biāo)位置。
int brute(char * mString ,char * subString) { int i = 0 ,j = 0; int m = strlen(mString),
n = strlen(subString); while ( i < m &&j < n) { if (mString[i] == subString[j]) {
i++;
j++;
} else {
i -= j - 1;
j = 0;
}
}if (j >= n) return i - j; if
