字符串匹配的BF算法

蠻力算法 (BF算法)

---

蠻力算法(Brute-Force)，簡稱BF算法。

算法思想

BF算法的算法思想是：

從目標串T的的第一個字符起與模式串P的第一個字符比較。

若相等，則繼續對字符進行后續的比較；否則目標串從第二個字符起與模式串的第一個字符重新比較。

直至模式串中的每個字符依次和目標串中的一個連續的字符序列相等為止，此時稱為匹配成功，否則匹配失敗。

通過下圖示例，可一目了然：

算法性能

假設模式串的長度是m，目標串的長度是n。

最壞的情況是每遍比較都在最后出現不等，即沒變最多比較m次，最多比較n-m+1遍。

總的比較次數最多為m(n-m+1)，因此BF算法的時間復雜度為O(mn)。

BF算法中存在回溯，這影響到效率，因而在實際應用中很少采用。

以下為代碼演示：

C語言代碼如下所示：

#include <stdio.h>
int BF(char S[],char T[])
{
    int index=0;
    int i=0;
    int j=0;
    while(S[i]!='\0'&&T[j]!='\0')
    {
        if(S[i]==T[j])
        {
        //如果匹配成功，則繼續比較下一對字符
            i++;
            j++;
        }
        else
        {
          //如果匹配不成功，主串和子串回溯坐標。index記錄的是每次匹配時的開始位置
            index++;
            i=index;
            j=0;
        }
    }
    if(T[j]=='\0') return index+1;
    else return 0;
}
int main()
{
    char a[30];
    printf("請輸入主串:");
    gets(a);
    char b[10];
    printf("請輸入子串:");
    gets(b);
    printf("匹配的開始位置是：%d",BF(a,b));
    return 0;
}

運行效果圖：

C++代碼如下：

#include <iostream>
#include <string.h>
using namespace std;
int BF(string S,string T)
{
    int index=0;
    int i=0;
    int j=0;
    while(S[i]!='\0'&&T[j]!='\0')
    {
        if(S[i]==T[j])
        {
            i++;
            j++;
        }
        else
        {
            index++;
            i=index;
            j=0;
        }
    }
    if(T[j]=='\0') return index+1;
    else return 0;
}
int main()
{
    string A;
    cout<<"請輸入主串:";
    cin>>A;
    string B;
    cout<<"請輸入子串:";
    cin>>B;
    cout<<"串在主串首次匹配的位置是:"<<BF(A,B)<<endl;
    return 0;
}

運行效果圖：