在使用KMP算法之前，使用了BF算法用于串匹配：原文鏈接已無法查找.....
設有主串s和子串t，子串t的定位就是要在主串s中找到一個與子串t相等的子串。通常把主串s稱為目標串，把子串t稱為模式串，因此定位也稱作模式匹配。模式匹配成功是指在目標串s中找到一個模式串t；不成功則指目標串s中不存在模式串t。
以下算法假設串采用順序存儲結構，即： #define MAXSIZE 50 typedef struct {char data[MAXSIZE];int length;}SqString; Brute-Force算法 Brute-Force算法簡稱為BF算法，亦稱為簡單匹配算法，其基本思路是：從目標串s的第一個字符開始和模式串t中的第一個字符比較，若相等，則繼續逐個比較后續的字符；否則從目標串s的第二個字符開始重新與模式串t的第一個字符進行比較。以此類推，若從模式串t的第i個字符開始，每個字符依次和目標串s中的對應字符相等，則匹配成功，該算法返回i；否則，匹配失敗，算法返回-1 。
該算法C實現代碼如下： int BFIndex(SqString *sp, SqString *tp) {int i, j;if(sp->length >= tp->length){for(i = 0; i < sp->length; i++){for(j = 0; j < tp->length && (i+j) < sp->length && sp->data[i+j] == tp->data[j]; j++);if(j == tp->length) return(i);}}return(-1);} 該算法的時間復雜度分析： 假設目標串s的長度為m，模式串t的長度為n。第一個for循環的語句頻度為m，第二個for循環的語句頻度為n，故該算法的時間復雜度為O(mn)，當然這是最壞的情況。該算法在最好情況下的時間復雜度為O(n)。 該算法比較簡單，易于理解，但效率不高，主要原因是：主串指針在若干字符序列比較相等后，若有一個字符比較不相等，需要回溯（主串指針的變化 i -> i+j -> i，回溯體現在i+j -> i這個過程，因為主串指針在第一個for循環每次執行i++時，都由i+j變為i，當然i+j >= i）。

例程：
/** file: Brute-Force.c* author: Jesse* date: 2011/08/07 13:15*/ #include <stdio.h> #define MAXSIZE 50 typedef struct{char data[MAXSIZE];int length;}SqString;int BFIndex(SqString *sp, SqString *tp){int i, j;if(sp->length >= tp->length){for(i = 0; i < sp->length; i++){for(j = 0; j < tp->length && (i+j) < sp->length && sp->data[i+j] == tp->data[j]; j++);if(j == tp->length) return(i);}}return(-1);} int main(void) {SqString s, t;int index;printf("\n請輸入目標串s和它的長度，以空格隔開，以回車鍵結束整個輸入：\n");scanf("%s %d", s.data, &s.length);printf("請輸入模式串t和它的長度，以空格隔開，以回車鍵結束整個輸入：\n");scanf("%s %d", t.data, &t.length);index = BFIndex(&s, &t);if(-1 == index) printf("\n匹配失敗！\n");else printf("\n匹配成功！ i = %d\n", index);return(0);}

總結

以上是生活随笔為你收集整理的时序分析：串匹配—Brute-Force算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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