串比對算法——BF算法

串比對問題:

串模式比對，簡稱串比對，是資料結構中的經典問題，在鄧俊輝版資料結構中，他的定義如下：

對基于同一字元表的任何文本串T（|T| = n）和模式串P（|P| = m），判定T中是否存在某一子串與P相同，若存在（比對），則報告該子串在T中的起始位置。

一般來說文本串T的長度n要遠大于模式串P的長度m。到目前為止，有五花八門各種各樣的串比對算法，下面介紹一種最簡單的蠻力算法。

蠻力算法(Brute Force)

在所有字元串比對算法中，BF算法是最直接，最符合人直覺的算法，它隻需要順序地從文本串T中截取長度為m的子串t，再将這個子串和模式串P逐字母的比較就可以了。

選取子串

用兩個指針i和j分别指向子串和模式串，比較對應的字元

如果對應的字元相等，如圖，$t[i] = P[j]$,則i和j各自前進一位。

如果$t[i] \ne P[j]$，說明該子串和模式串不比對

于是放棄該子串，在T中順序選擇下一個子串，重新開始上面的比對過程。

當指向模式串P的指針j周遊完模式串後，說明所有的字元都比對成功，那這個子串就找到了，傳回這個位置就可以了。

字元串比對的代碼如下:

1 #include<stdio.h>
 2 #include<string.h>
 3 int BF(char*T,char*P)
 4 {
 5     int i,j;
 6     int m = strlen(P),n = strlen(T);
 7     printf("%d %d\n",m,n);
 8     i = j =0;
 9     while(j<m&&i<n)
10     {
11         if(P[j]==T[i])
12             i++,j++;
13         else
14         {
15             i = i-j+1;
16             j = 0;
17         }
18         if(j==m)
19             return i-j;
20     }
21     return -1;
22 }
23 int main()
24 {
25     char*T = "ABCDESABCDFAB";
26     char*P = "ABCDF";
27     int indexof = BF(T,P);
28     printf("%d\n",indexof);
29     return 0;
30 }

時間複雜度分析

不難發現，文本串T至多有n-m+1個子串，每輪最多進行m次計較，是以最多需要比較$m*(n-m+1)$次，是以它的時間複雜度為$O(nm)$。最好的情況是每經一次比對就發現不比對，這種情況下，BF算法的時間複雜度下降為$O(n)$，但是這種情況比較難出現。

BF算法雖然簡單，但是在最壞情況下所需的時間，是文本串長度和字元串長度的乘積，當文本串很長時，它的時間複雜度會非常高，是以我們需要更加高效的算法。下一篇部落格将介紹更高效的KMP算法。

發表于

2021-03-29 21:30

行運換甲

閱讀(116)

評論(0)

編輯

舉報