BF算法介紹

BF算法，即暴風(fēng)(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是將目標(biāo)串S的第一個字符與模式串T的第一個字符進行匹配，若相等，則繼續(xù)比較S的第二個字符和 T的第二個字符；若不相等，則比較S的第二個字符和T的第一個字符，依次比較下去，直到得出最后的匹配結(jié)果。BF算法是一種蠻力算法。

BF算法分析

算法思想很簡單，就是子串的第一位可主串進行比較，如果相等，然后下一位進行比較，遇到不相等，主串從開始比較的哪一位的下一位和子串第一位進行比較，直到出現(xiàn)匹配結(jié)果。寫法有很多種，只要思想ok，就可以寫出來。

代碼展示

下面采用c語言進行實現(xiàn)，函數(shù)返回的是子串在主串中的index。

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h>int IndexSubString(char* dest_str,char* sub_str,int begin) {if (begin < 0){begin = 0;}char* dest = dest_str + begin;char* sub = sub_str;//通過字符一個一個進行比較while (*dest != 0){//和子串第一個字符不相等if (*dest != *sub){dest++;continue;}char* temp = dest;//走到這里主串和子串第一個字符相等，繼續(xù)往下進行比較sub++;dest++;//遇到不相等的字符就回溯，主串回溯到標(biāo)記的下一位繼續(xù)和子串的第一位開始進行比較while (*sub != 0){if (*sub == *dest){sub++;dest++;}else{sub = sub_str;dest = temp + 1;break;}}//判斷子串是否遍歷完畢,返回位置if (*sub == 0){return dest - dest_str - strlen(sub_str);}}return -1; }//brute force BF算法又稱，暴風(fēng)算法，普通的模式匹配算法 int main_BF(int argc, char *argv[]) {char dest[100] = { 0 }, sub[100] = { 0 }, num[5] = {0};int begin = 0;while (1){memset(dest, 0, 100);memset(sub, 0, 100);memset(num, 0, 5);printf("請輸入目標(biāo)字符串(#退出):");fgets(dest, 100, stdin);dest[strlen(dest)-1] = 0;//去掉換行符if (strcmp(dest,"#")==0){break;}printf("請輸入查詢起始位置(不輸入從0開始):");fgets(num, 5, stdin);if (strlen(num) != 1){num[strlen(num) - 1] = 0;//去掉換行符sscanf(num, "%d", &begin);}printf("請輸入查詢子串:");fgets(sub, 100, stdin);sub[strlen(sub) - 1] = 0;//去掉換行符int index = IndexSubString(dest, sub, begin);printf("dest=%s,sub=%s,begin=%d,index=%d\n", dest, sub, begin,index);}return 0; }

運行檢測

總結(jié)

以上是生活随笔為你收集整理的字符串：BF算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。