基本思想：

其基本思想是從主串的第一個字符起與模式串的第一個字符比較，若相等，則繼續逐個字符的后續比較，否則從主串的第二個字符起與模式串的第一個字符重新開始比較，直至模式串中的每個字符依次和主串中的一個連續的字符序列相等時為止，此時稱為匹配成功，否則稱為匹配失敗。

以字符數組存儲字符串，實現樸素的模式匹配算法。

1 int Index(char S[], char T[], int pos) 2 /*查找并返回模式串T在主串S中從pos開始的位置(下標)，若T不是S的子串，則返回-1 */ 3 { 4 i = pos; j=0; // i , j 分別用于指示出主串字符和模式串字符的位置(下標) 5 slen = strlen(S); tlen = strlen(T); //計算主串和模式串的長度 6 while(i < slen && j <tlen) 7 { 8 if(S[i] == T[j]) 9 { 10 i++;j++; 11 } 12 else 13 { 14 i = i - j + 1; //主串字符的位置指針回退 15 j = 0; 16 } 17 } 18 if(j >= tlen) //匹配成功 19 return i - tlen; 20 return -1; //匹配失敗，返回 - 1 21 }

時間復雜度：

在最好的情況下匹配算法的時間復雜度為O(n + m).最壞的情況下的時間復雜度為O( n?× m)，對該算法進行改進的模式匹配算法又稱為KMP算法，其改進之處在于：每當匹配過程中出現相比較的字符不相等時，不需要回溯主串字符的位置指針。而是利用已經得到的“部分匹配”的結果，將模式串向后“滑動”盡可能遠的距離，再繼續進行比較。

轉載于:https://www.cnblogs.com/xiehuan-blog/p/9011782.html

總結

以上是生活随笔為你收集整理的字符串处理：布鲁特--福斯算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。