字符串匹配
假設(shè)有兩個串s和p，字符串匹配就是在s中查找與p相同的子串的操作。將s稱為目標(biāo)串，p稱為模式串。
BF
BF(Brute Force)算法又稱為暴力匹配算法。將p與s的所有的子串進行匹配。最壞情況O(m*n)。
// return: first match index of s
int bf_match(char const * s, char const * p)
{
int p_len = strlen(p);
int max_s_len = strlen(s) - p_len + 1;
int s_ind = 0;
int p_ind = 0;
while (s_ind < max_s_len && p_ind < p_len)
{
if (s[s_ind] == p[p_ind])
{
s_ind++;
p_ind++;
}
else
{
s_ind = s_ind - p_ind + 1;
p_ind = 0;
}
}
return p_ind == p_len ? s_ind : -1;
}
KMP
Knuth-Morris-Pratt字符串查找算法，簡稱為 “KMP算法”由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年聯(lián)合發(fā)表。
Part 1
定義：綠色為SP匹配部分；紅色為SP不匹配部分，此時的下標(biāo)S[j]，P[i]，并且P[0:i-1] == S[j-i:j-1]。
bf算法的最大問題是：不會跳過無意義的步驟。如下圖，在S[4]:e和P[4]:f匹配失敗后，P[0]:a依然和S[1:3]依次進行匹配，做無用功。
結(jié)論1：匹配部分長度大于0(i>0)，如果P[0]在當(dāng)前P[0:i-1]只出現(xiàn)一次，那么去匹配P[0]和S[j]；匹配部分長度等于0(i=0)，P[0] != S[j]，那么去匹配P[0]和S[j+1]。
Part 2
如下圖，與結(jié)論1相反，在匹配部分出現(xiàn)多次P[0]:a是P[2]和P[4]，在S[6]:e和P[6]:f處匹配失敗。
如下圖，如果將P[0]:a與S[2]:a匹配，會在P[1]:b和S[3]:c處匹配失敗，那么現(xiàn)在的情況又回到了結(jié)論1，將會進行P[0]:a與S[3]:c匹配，一樣會失敗。所以，這樣的匹配會進行多次的無用功。在S[6]:e與P[6]:f匹配失敗時就可以觀察到P[0]:a與S[2]:a匹配最終一定會失敗的，這個信息是在P[6]:f匹配失敗時通過P串就能獲得的，并不需要S串。
如下圖，如果將P[0]:a與S[4]:a匹配，P[1]:b和S[5]:b也是匹配的，在S[6]:e與P[6]:f匹配失敗時就可以觀察到P[0]:a,b與S[4]:a,b匹配，這個信息是在P[6]:f匹配失敗時就能獲得的，并不需要S串。至于P[2]和S[6]是否匹配需要進行，不能單靠P[6]:f匹配失敗時的P串獲得這個信息。
如上圖，這個匹配方法相比于bf跳過了P[0]與S[1:5]的比較，P[0]:a,b與S[4]:a,b是不需要匹配的，直接進行P[2]:a與S[6]:e的匹配，S串不進行回溯，P串進行短回溯。重點是如何找到這樣的位置進行匹配：
∵ S[6]:e != P[6]:f
∴ S[0:5] == P[0:5]
export 0 <= n <= 4
if S[0:n] == P[0:n] && S[5-n:5] == P[0:n]
then P[0:n] == P[5-n:5]
結(jié)論2：P[i]匹配失敗，i > 1 && 0 <= n <= i-2，如果存在P[0:n] == P[i-1-n:i-1]，就是P[0:i-1]存在一個前綴和后綴是相同的，那么進行P[n+1]與S[j]匹配。
為什么是P[n+1]？觀察上圖，n == 1，前綴P[0:1]的長度為2，需要和S[6]進行匹配的P的下標(biāo)也是2，都剛好是n+1。結(jié)論是，如果存在前綴，則進行P[前綴長度]和S[j]的匹配。
Part 3
如上圖，根據(jù)結(jié)論2會出現(xiàn)下圖兩種情況都滿足。
按照從S左到右的匹配順序，不應(yīng)該錯過P[0]與S[2]對齊時的P[4]與S[6]的匹配，直接進行P[0]與S[4]對齊時的P[2]與S[6]的匹配。在多種情況時，應(yīng)該選擇P[0]與S[最小能夠?qū)R的下標(biāo)]進行對齊。
結(jié)論3：應(yīng)該選擇滿足 結(jié)論2 并且是最長的相同前后綴。
觀察上圖，在P[0]與S[2]對齊的匹配失敗后，會自然落到P[0]與S[4]對齊的情況。
Part 4
基于以上結(jié)論，在P[i]和S[j]在匹配失敗后，S串不回溯，P串回溯到i等于P[0:i-1]的最長相等前后綴長度。
現(xiàn)在需要構(gòu)造一個next數(shù)組，使得在P[i]匹配失敗后通過next[i]獲得P[0:i-1]的前綴長度。
static int * get_next(char const *p);
// return: first match index of s
int kmp_match(char const *s, char const *p)
{
int p_len = strlen(p);
int max_s_len = strlen(s) - p_len + 1;
int s_ind = 0;
int p_ind = 0;
int *next = _get_next(p);
while (s_ind < max_s_len && p_ind < p_len)
{
if (s[s_ind] == p[p_ind])
{
s_ind++;
p_ind++;
}
else
{
//=======================
// s_ind = s_ind - p_ind + 1;
p_ind = next[p_ind];
//=======================
}
}
free(next);
return p_ind == p_len ? s_ind : -1;
}
上面的kmp_match是通過bf_match改造的：s_ind不變，p_ind回溯。
但是存在一個bug，已知P[0]匹配失敗時的前綴長度是0，按照 結(jié)論1 是P[0]去和S[j+1]匹配，匹配失敗的代碼是:
else
{
//=======================
// s_ind = s_ind - p_ind + 1;
p_ind = next[p_ind];
//=======================
}
p_ind是0沒有問題，但是s_ind沒有更新，進入下一次循環(huán)還是P[0]和S[j]匹配，那么while是一直原地踏步。
應(yīng)該增加一條P[0]匹配失敗的條件分支，則：
if (s[s_ind] == p[p_ind])
{
// 匹配成功
s_ind++;
p_ind++;
}
else if (p_ind)
{
// 匹配失敗，并且i=0時，更新j為j+1
s_ind++;
}
else
{
// 匹配失敗，更新i，如果i=0，依舊更新為0
//=======================
// s_ind = s_ind - p_ind + 1;
p_ind = next[p_ind];
//=======================
}
為了簡化代碼，規(guī)定P[0]匹配失敗時的前綴長度(next[0])為-1，則：
if (p_ind == -1 || s[s_ind] == p[p_ind])
{
// i=-1時，二次進入將i更新為0，j更新為j+1
s_ind++;
p_ind++;
}
else
{
// 匹配失敗，更新i，如果i=0，更新為-1
p_ind = next[p_ind];
}
只看這段代碼：只要進入循環(huán)時i == -1, 那么i = 0, j++。
Part 5
構(gòu)造next數(shù)組有兩種方式：1. 暴力構(gòu)造；2.遞推構(gòu)造
原理：next[i]是P[i]匹配失敗時P[0:i-1]的最長相等前后綴的長度。
暴力構(gòu)造
static int _strcmp(
const char *p,
unsigned int len,
unsigned int index_1,
unsigned int index_2
)
{
int cnt = 0;
while (p[index_1] - p[index_2] == 0 && cnt < len) {
index_1++;
index_2++;
cnt++;
}
return cnt == len ? 1 : 0;
}
static int * _get_next(char const *p)
{
int p_len = strlen(p);
int *next = malloc(sizeof(int) * p_len);
next[0] = -1;
unsigned int next_ind = 1;
unsigned int substr_len;
unsigned int max_preffix_len;
for (; next_ind < p_len; next_ind++)
{
substr_len = next_ind;
max_preffix_len = sub_str_len - 1; // 從最長的前綴和后綴開始
while (max_preffix_len > 0)
{
if (_strcmp(p, max_preffix_len, 0
, substr_len - max_preffix_len))
{
break;
} else {
max_preffix_len--;
}
}
next[next_ind] = max_preffix_len;
}
return next;
}
遞推構(gòu)造
原理：根據(jù)前面構(gòu)造好的最長前后綴長度推出這個前綴長度。
上圖中，無論?處是多少，next[11]都應(yīng)該是5，那??處該是多少。
P[11]最長相等前后綴的長度為5，如果P[11] == P[5]，如下圖，那會出現(xiàn)P[0:5] == P[6:11] ，相當(dāng)于將P[0:4] == P[6:10]等式兩邊都延長一個單位，等同于next[12] = next[11] + 1。
遞推結(jié)論1：如果i > 1 && P[next[i-1]] == P[i-1], 那么next[i] = next[i-1] + 1。
如果P[11] != P[5]，那上面的情況是沒戲了。那就找比最長短一點的，需要在最長前綴P[0:4]中找一個前綴，在最長后綴P[6:10]中找一個后綴。如下圖。
因為P[0:4] == P[6:10]，所以就相當(dāng)于在P[0:4]中找一對最長前后綴，如下圖，前綴長度顯然存放在next[5]中。
此時，如果P[11] == P[2]，那么next[12] = next[5] + 1。如下圖。
如果P[11] != P[2]，像P[11] != P[2]一樣。那就找更短一點的，需要在前綴P[0:1]中找一個前綴，在最長后綴P[9:10]中找一個后綴。
因為P[0:1] == P[9:10]，所以就相當(dāng)于在P[0:1]中找一對最長前后綴，如下圖，前綴長度顯然存放在next[2]中。
此時，如果P[11] == P[0]，那么next[12] = next[2] + 1。如下圖。
如果P[11] != P[0]，已經(jīng)沒有更短的前后綴了，next[12] = next[0] + 1 = -1 + 1 = 0。
遞推結(jié)論2：如下圖，為得到next[i]，需要P[i-1]的最長前后綴，如果P[i-1] == P[next[i-1]]，那么next[i] = next[i-1] + 1；如果不相等，找第二長的前后綴，如果P[i-1] == P[next[next[i-1]]], next[i] = next[next[i-1]] + 1; ...直到最后沒有前后綴，P[i-1] == P[0], 則next[i] = 0 + 1, 這個0是在圖中next[2]這樣得來的，P[i-1] != P[0], 則next[i] = -1 + 1 = 0。
在過程中好像一直在找更短的前后綴，使得滿足P[i-1] == P[前后綴長度]，致使P[i]得到最長的前后綴長度。實際只測試了條件，不滿足就去找更短的前后綴長度來測試條件，前后綴長度之間的關(guān)系：next[當(dāng)前前后綴長度] == 更短的前后綴長度。
代碼實現(xiàn)：
static int * _get_next(char const *p)
{
int p_len = strlen(p);
int *next = malloc(sizeof(int) * p_len);
next[0] = -1; // P[0]的next[0]
int index = 1; // next數(shù)組當(dāng)前索引，需要求next[index]
// k為next[index-1]，求next[index]時需要next[index-1]遞推
int k = next[0];
while (index < p_len)
{
if (k == -1) // P[i-1]不等于P[0]，或i=1時，當(dāng)前的前綴長度更新為0;
{
next[index] = k + 1;
index++;
k++;
// index++，原k=next[index-1]，更新為k=next[index]
}
// k=next[index-1]，匹配p[index - 1]和p[index-1的前綴長度]
else if (p[index - 1] == p[k])
{
next[index] = k + 1;
index++;
k++;
}
else
{
// 更新k為更短的前綴長度，在p[index-1] != p[k]且k=0時，會將k更新為-1
k = next[k] ;
}
}
return next;
}
// 合并前兩個分支
static int * _get_next(char const *p)
{
int p_len = strlen(p);
int *next = malloc(sizeof(int) * p_len);
next[0] = -1;
int index = 1;
int k = -1;
while (index < p_len)
{
if (k == -1 || p[index - 1] == p[k])
{
next[index] = k + 1;
index++;
k++;
}
else
{
k = next[k] ;
}
}
return next;
}
// 優(yōu)化index，從求next[index]變成求next[index+1]
static int * _get_next(char const *p)
{
int p_len = strlen(p);
int *next = malloc(sizeof(int) * p_len);
next[0] = -1;
int index = 0; // 從0開始
int k = -1;
while (index < p_len - 1)
{
if (k == -1 || p[index] == p[k])
{
index++;
k++;
next[index] = k;
}
else
{
k = next[k] ;
}
}
return next;
}
優(yōu)化，連續(xù)失敗情況：
上圖中，在S[j]:?和P[11]處匹配失敗，d != ?，下一步應(yīng)該將P[5]和S[j]:? 匹配。觀察得出P[5] == P[11]，那么P[5]和S[j]:?是一定匹配失敗的。
也就是在P[i]處的匹配失敗時，如果P[next[i]] == P[i]，那么P[next[i]]也一定是匹配失敗的。這樣說明構(gòu)建的next數(shù)組是不合理的，所以在P[i] == P[next[i]]時，應(yīng)該構(gòu)建短一點的前后綴。如下圖。
上圖，將next[11]設(shè)置為2更合理。疑問：如果P[2]不是c，也是d怎么辦？
上圖中，無論是將next[11]設(shè)置為8、5、2都會匹配失敗，應(yīng)該設(shè)為0。但是這是反向遞推，需要next回退幾步；實際正向遞推是這樣：
得到next[2]=0，就得到next[5]，next[8]，next[11]。
優(yōu)化后的方法：
static int * _get_next(char const *p)
{
int p_len = strlen(p);
int *next = malloc(sizeof(int) * p_len);
next[0] = -1;
int index = 0; // 從0開始
int k = -1;
while (index < p_len - 1)
{
if (k == -1 || p[index] == p[k])
{
index++;
k++;
// next[index] = k; 會出現(xiàn)p[next[index]] = p[index]連續(xù)失敗的情況
if (p[index] != p[k])
{
next[index] = k;
}
else
{
// p[index] == p[k]時，回退一步k
next[index] = next[k];
}
}
else
{
k = next[k] ;
}
}
return next;
}
說明next出現(xiàn)非索引0處為-1的情況：
在上上面的kmp算法 結(jié)論1 中，next[i]=-1時，使i=0，j++；就是出現(xiàn)了P[0]處匹配失敗。如下圖：
圖中，P[3]和P[6]都是前綴長度為0，匹配S[j]失敗時，原本都是和P[0]再進行匹配，又因為P[3]和P[6]都等于P[0]，所以next[3]和next[6]都應(yīng)該等于-1，使得進行P[0]和S[j+1]匹配。
在next數(shù)組構(gòu)造中體現(xiàn)于：
if (p[index] != p[k])
{
next[index] = k;
}
else
{
// 在p[index] == p[0]時，next[index] = next[0] = -1
next[index] = next[k];
}
Sunday
Sunday算法是DanielM.Sunday于1990年提出的字符串模式匹配。
在S串和P串存在匹配的字串s，必然有s == P，如果S串中包含P串沒有的字符k，那么s中一定不包含k。Sunday算法就是基于這個事實。
上圖中，P串中不包含字符S[5]，那么P與S匹配的情況可能是P1、P2、P3，絕不可能是P4。
Part 1
上圖中，P串長度為7，與S串在P[4]處匹配失敗，接下來P串要相對S串向后移一位?，F(xiàn)在的問題是P串中是否包含S[7]？
上圖中，P不包含字符S[7]，那么P串與S串處于上圖中P1~7狀態(tài)的對齊匹配都是會與S[7]匹配失敗，只有在P8狀態(tài)跳過與S[7]的匹配是有可能成功的。
結(jié)論1：P串長為length，P[0]與S[k]對齊進行匹配，在P串的任何匹配失敗時，如果P串不包含字符S[k+length]，則P[0]與S[k+length+1]對齊匹配。
Part 2
如果P串中包含S[7]呢？如上圖，P[1]、P[3]、P[5]都等于S[7]。
在上圖中，S[7]與P[1]、P[3]、P[5]對齊時的P2、P4、P6狀態(tài)都是有可能匹配成功的，而P1、P3、P5、P7對齊狀態(tài)是絕不可能匹配成功的。
按照匹配順序，P2狀態(tài)是步幅最小的、合理的。
結(jié)論2：P串長為length，P[0]與S[k]對齊進行匹配，在P串的任何匹配失敗時，如果P串包含字符S[k+length]，則S[k+length]與其在P串中最右出現(xiàn)的位置對齊，從P[0]匹配。
// return a hash table, key : byte, val : the byte in rightest
static int * _get_rightest(char const *p);
// return: first match index of s
int sunday_match(char const *s, char const *p)
{
int p_len = strlen(p);
int max_s_len = strlen(s) - p_len + 1;
int s_ind = 0;
int p_ind = 0;
int *rightest = _get_rightest(p);
while (s_ind < max_s_len && p_ind < p_len)
{
if (s[s_ind] == p[p_ind])
{
s_ind++;
p_ind++;
}
else
{
// 獲取匹配失敗時，類似上面S[7]位置的byte
int ac_index_s = s_ind + p_len - p_ind;
unsigned char ac = s[ac_index_s];
// ac字符在p串最右面的出現(xiàn)的位置
int ac_index_rp = rightest[ac];
if (index == -1)
{
// ac在p串中不存在，S串在ac字符的下一個字符開始比較
s_ind = ac_index_s + 1;
}
else
{
// 將ac與p[ac_index_rp]對齊
s_ind = ac_index_s - ac_index_rp;
}
p_ind = 0;
}
}
free(rightest);
return p_ind == p_len ? s_ind : -1;
}
Part 3
結(jié)論2需要一個統(tǒng)計P串中所有出現(xiàn)的字符和其在P串中最右邊出現(xiàn)的位置。
c中的字符編碼問題：linux64位c默認(rèn)是使用utf-8編碼，中英文占用字節(jié)不等長，沒有高級api的加持很難統(tǒng)計，在匹配字符的情況下；如果，只是看作是字節(jié)匹配，那么無論什么編碼都沒關(guān)系，只要S串和P串的編碼相同，并且在字節(jié)匹配最多有255種字節(jié)。linux64位下wchar_t是4個字節(jié)，按字符統(tǒng)計的效率更高，在utf-16編碼的情況下字符大概有65535種，但是S串和P串可能需要向wchar_t轉(zhuǎn)換。
// 無符號字符為index, 在p中出現(xiàn)的最右位置為值
static int * _get_rightest(char const *p)
{
int p_len = strlen(p);
int *char_on_rightest = mollac(sizeof(int) * 256);
int i;
for (i = 0; i < 256; i++)
{
char_on_rightest[i] = -1; // -1代表p中不存在等于i的字節(jié)
}
for (i = 0; i < p_len; i++)
{
char_on_rightest[p[i]] = i;
}
return char_on_rightest;
}
BM
1977年，德克薩斯大學(xué)的Robert S. Boyer教授和J Strother Moore教授發(fā)明了這種算法。
Sunday算法是在BM算法的基礎(chǔ)之后出現(xiàn)的，并且有相通的思想。
Part 1
BM算法的匹配順序是從P[m-1]向P[0]方向匹配，P串從S串頭向S串尾對齊。
Part 2
壞字符規(guī)則，這個思想和Sunday的思想是一致的，但是還沒有Sunday算法完善。
上圖中在P[3]:c處匹配失敗，S[3]:a就叫壞字符。接下來P向后移，如果P[0]、P[1]、P[2]都不等于a，P[0]與P[4]對齊；多個等于a的，S[3]就和P位置小于3且靠右的a對齊。
上圖中，P1[2]與S[3]對齊，這是理想的方式：實現(xiàn)時，如果S[j]和P[i]不匹配，那就要遍歷P[0:i-1]尋找P[?]等于S[j]，或者記錄P中所有字符在P串中的出現(xiàn)的所有的位置。按照這種理想實現(xiàn)的壞字符規(guī)則是在Horspool算法中，也只用這種規(guī)則。
實際上，只記錄了P的中所有字符及其在P中最右出現(xiàn)的位置，和Sunday算法構(gòu)造的字符位置hash數(shù)組是一樣的。所以：
在BM算法中，壞字符規(guī)則會出現(xiàn)P相對S反向移動對齊。顯然，這個規(guī)則是不足以支撐算法的，所以需要一個規(guī)則——好后綴規(guī)則。
BM算法的壞字符規(guī)則的最壞情況：
上圖中，在S[1]和S[2]處循環(huán)連續(xù)失敗。Sunday算法的壞字符在上圖在P1情況下會選擇S[6]為壞字符，在P2情況下選擇S[5]為壞字符，所以P相對S的位移永遠是正向的。
Part 3
好后綴規(guī)則，和壞字符規(guī)則思想是一致的。
上圖中，在P[4]處匹配失敗，P[5:6]和S[5:6]匹配，那么P[5:6]就是好后綴。接下來P相對S向后移動，如果在P[0:5]中存在"ab"，"ab"應(yīng)該與S[5:6]對齊，存在多個"ab"取P[0:5]中最后一個；不存在P[0]與P[7]對齊。
P1在P[2:3]為"ab"，P2在P[0:5]中不包含"ab"。
另一種情況，如下圖：
在P1[5]處匹配失敗，P1[0:7]中不包含"abc"，但是存在P1前綴"bc"等于好后綴"abc"的子后綴"bc"，可以使P2[0:1]與S[7:8]對齊。
上圖中，在P1[0:7]存在"abc"，P相對S最短位移，P[3:5]應(yīng)與S[6:8]對齊。
結(jié)論：在P串存在與好后綴相同(但不是一個)的子串，子串與S串對齊；不存在與好后綴相同子串，如果存在與好后綴的子后綴相同的P串前綴，則前綴與S串對齊。
所以好后綴需要構(gòu)造一個子串位置表和相同前后綴表。
Part 4
Bm算法有壞字符和好后綴兩種規(guī)則，在P相對S移動時使用兩種規(guī)則中移動距離更遠的一個。
為什么是誰遠使用誰？
接下來的不滿足壞字符指P串中沒有出現(xiàn)該壞字符，不滿足好后綴指P串沒有出現(xiàn)子串等于該后綴也沒有前綴等于該后綴的子后綴。
不滿足壞字符 && 不滿足好后綴
匹配失敗時，按壞字符規(guī)則對齊為P1，但P[6:8]是不滿足好后綴規(guī)則的，P1的情況是注定匹配失敗的。P2是按照好后綴規(guī)則對齊的，是可能匹配成功的。
這種情況誰遠使用誰。
不滿足壞字符 && 滿足好后綴
情況1：子串等于好后綴，不是P前綴
P1是壞字符規(guī)則對齊，但是好后綴沒有對齊，P1是注定匹配失敗的；P2是好后綴規(guī)則對齊，但是P串中沒有壞字符，P[0]永遠不等于S[5]，P2是注定匹配失敗的。兩種情況都是失敗的：
這種情況誰遠使用誰。
情況2：子串等于好后綴，是P前綴
P1是壞字符規(guī)則對齊，并且P前綴等于好后綴；P2是好后綴規(guī)則對齊。兩種情況都是成功的：
這種情況誰遠使用誰。
情況3：前綴等于好后綴的子后綴
P1是壞字符規(guī)則對齊，但是好后綴沒有對齊，失??；P2是好后綴規(guī)則對齊，可能會匹配成功。
這種情況誰遠使用誰。
滿足壞字符 && 不滿足好后綴
情況1：壞字符只在P好后綴出現(xiàn)
P1串是壞字符規(guī)則對齊，相對S反向移動，失?。籔2是不滿足好后綴規(guī)則對齊，可能匹配成功。
這種情況誰遠使用誰。
情況2：壞字符只在P匹配失敗位置前出現(xiàn)
P1是滿足壞字符的最大位移情況，但不滿足好后綴規(guī)則注定失??；P2是不滿足好后綴規(guī)則對齊，可能匹配成功。
這種情況誰遠使用誰。
情況1附加：壞字符出現(xiàn)在好后綴和P匹配失敗位置前
壞字符表只記錄a在P[6]出現(xiàn)，沒有記錄P[2]處出現(xiàn)的a；P1和P2是情況1正常的移位；P3是假設(shè)P[2]:a和S[5]對齊的情況，如圖，不滿足好后綴規(guī)則，P3不能匹配成功。
滿足壞字符 && 滿足好后綴
情況1：位移相同
壞字符和好后綴在S串是連續(xù)的，在P串也是連續(xù)的，具有相同的位移。
這種情況誰遠使用誰。
情況2：壞字符——間隔——好后綴
這種情況下，P1壞字符對齊則好后綴對不齊，P2好后綴對齊則壞字符對不齊。兩種情況都會失敗。
如果把P[1]:e替換成"abc"，那么P1就可能成功。如果把P[1]:a替換成"k"，那么就是情況1。
這種情況誰遠使用誰。
情況3：好后綴——間隔——壞字符
P1壞字符對齊時，好后綴沒有對齊，注定失敗；P2是好后綴對齊，?處可能是等于壞字符的，P2是有可能匹配成功的。
這種情況誰遠使用誰。
綜上所述：在BM算法中，壞字符規(guī)則和好后綴規(guī)則量誰移動的距離遠，就使用那個規(guī)則。在兩種規(guī)則中好后綴規(guī)則是占主體的。
Part 5
構(gòu)造BM算法需要一個壞字符表，一個好后綴表，一個相等前后綴表。
好后綴表以后綴長度為索引，以與其在P串最右的相等串的首索引為值。
相等前后綴表以后綴長度為索引，以0和1表示是否有前綴等于該后綴。
// return a hash table, key : byte, val : the index in rightest, -1 prefom no byte in p
static int * _get_bad_chars(char const *p);
// return a hash table, key : length of suffix, val : the index in rightest of substr equal suffix, -1 preform no substr equal suffix
static int * _get_good_suffixs(char const *p);
// return a hash table, key : length of suffix, val : 0 perform no prefix equal suffix, 1 perform a prefix equal suffix
static int * _get_prefix_equ_suffix(char const *p);
// return: first match index of s
int bm_match(char const *s, char const *p)
{
int p_len = strlen(p);
int s_len = strlen(s);
int p_ind = p_len - 1;
int s_ind = p_ind;
int *bc_ht = _get_bad_chars(p);
int *gs_ht = _get_good_suffixs(p);
int *pes_ht = _get_good_prefix_equ_suffix(p);
while (s_ind < s_len && p_ind > -1)
{
if (s[s_ind] == p[p_ind])
{
s_ind--;
p_ind--;
}
else
{
// 獲取匹配失敗時的壞字符在P最右的位置
int bc_ind = bc_ht[s[s_ind]];
// 壞字符對齊時，P相對S移動距離
int bc_re_ins;
if (bc_ind != -1)
{
bc_re_ins = p_ind - bc_ind;
}
else
{
bc_re_ins = p_ind + 1; // P[0]與P[p_ind+1]對齊
}
// 獲取好后綴在P最右的位置
int gs_len = p_len - 1 - p_ind;
int gs_ind = gs_ht[gs_len];
// 好后綴對齊時，P相對S移動距離
int gs_re_ins;
if (gs_ind != -1)
{
gs_re_ins = p_ind + 1 - gs_ind;
}
else
{
// 沒有好后綴，查找相等前后綴
int pes_len = gs_len - 1;
while (pes_len > 0)
{
if (pes_ht[pes_len]) {
break;
}
pes_len--;
}
if (pes_len > 0)
{
// 有相等的前后綴
gs_re_ins = p_len - pes_len; // P[0]與P[p_len - pes_len]對齊
}
else
{
// 沒有相等的前后綴
gs_re_ins = p_len; // P[0]與P[p_len]對齊
}
}
// 壞字符與好后綴中最大的相對位移。
int max_re_ins = max(bc_re_ins, gs_re_ins);
// 找到現(xiàn)在與P[0]對齊的S[j]
int j = s_ind - p_ind;
s_ind = j + max_re_ins + p_len;
p_ind = p_len - 1;
}
}
free(bc_ht);
free(gs_ht);
free(pes_ht);
return p_ind ? -1 : s_ind;
}
優(yōu)化點是：好后綴表為-1時，P相對S的位移一定是最大的，這時不需要壞字符。
Part 6
壞字符表
完全復(fù)制Sunday表
// return a hash table, key : byte, val : the index in rightest, -1 prefom no byte in p
static int * _get_bad_chars(char const *p)
{
int p_len = strlen(p);
int *bc = malloc(sizeof(int) * 256);
int i;
for (i = 0; i < 256; i++)
{
bc[i] = -1; // -1代表p中不存在等于i的字節(jié)
}
for (i = 0; i < p_len; i++)
{
bc[p[i]] == i;
}
return char_on_rightest;
}
好后綴表
// return a hash table, key : length of suffix, val : the index in rightest of substr equal suffix, -1 preform no substr equal suffix
static int * _get_good_suffixs(char const *p)
{
int p_len = strlen(p);
int *gs = malloc(sizeof(int) * p_len);
int i = 0;
for (; i < p_len; i++)
{
gs[i] = -1;
}
i = 0;
const int last = p_len -1;
while (i < last)
{
int l_cur = i, r_cur = last, substr_len = 0;
// 回溯
while (l_cur >= 0 && r_cur >= 0 && p[l_cur] == p[r_cur])
{
substr_len++
l_cur--;
r_cur--;
}
if (substr_len)
gs[substr_len] = i - substr_len + 1;
i++;
}
return gs;
}
// return a hash table, key : length of suffix, val : 0 perform no prefix equal suffix, 1 perform a prefix equal suffix
static int * _get_prefix_equ_suffix(char const *p)
{
int p_len = strlen(p);
int *pes = malloc(sizeof(int) * p_len);
int i = 0;
for (; i < p_len; i++)
{
pes[i] = 0;
}
i = 0;
const int last = p_len -1;
while (i < last)
{
int l_cur = i, r_cur = last;
// 回溯
while (l_cur >= 0 && r_cur >= 0 && p[l_cur] == p[r_cur])
{
l_cur--;
r_cur--;
}
if (l_cur == -1)
pes[i+1] = 1;
i++;
}
}
合并3個表的方法
struct Bgp {
int *bc;
int *gs;
int *pes;
}
static struct Bgp * _get_all(const char *p)
{
int p_len = strlen(p);
struct Bgp *bgp = malloc(sizeof(struct Bgp));
int *bc= malloc(sizeof(int) * 256);
int *gs = malloc(sizeof(int) * p_len);
int *pes = malloc(sizeof(int) * p_len);
bgp->bc = bc;
bgp->gs = gs;
bgp->pes = pes;
int i;
for (i = 0; i < 256; i++)
bc[i] = -1;
for (i = 0; i < p_len; i++)
{
gs[i] = -1;
pes[i] = 0;
}
i = 0;
const int last = p_len -1;
while (i < last)
{
int l_cur = i, r_cur = last, substr_len = 0;
// 回溯
while (l_cur >= 0 && r_cur >= 0 && p[l_cur] == p[r_cur])
{
substr_len++
l_cur--;
r_cur--;
}
if (substr_len)
gs[substr_len] = i - substr_len + 1;
if (l_cur == -1)
pes[i+1] = 1;
bc[p[i]] = i;
i++;
}
bc[p[last]] = last;
return bgp;
}
總結(jié)
KMP、SUNDAY、BM字符串匹配算法。KMP只汲取P串自身的信息；SUNDAY算法汲取P和S的信息；BM汲取更多P和S的信息。
模式串長度為m，目標(biāo)串長度為n。
則KMP的時間復(fù)雜度為O(m+n)，穩(wěn)定。
SUNDAY和BM算法的搜索最優(yōu)時間復(fù)雜度為O(n/m)，就是一匹配就失敗并且壞字符不在模式串中，最差時間復(fù)雜度為O(m*n)，總是在模式串匹配到最后一位(BM是第一位)的失敗，并且壞字符(BM還有好后綴)總是在比較后的位置。
SUNDAY的構(gòu)造時間復(fù)雜度為O(m + 字符集大小)，BM算法的構(gòu)造時間復(fù)雜度為O(m + 字符集大小 + m ^ 2)。字符集越大，BM和SUNDAY越優(yōu)， 因為壞字符不在模式串的可能性越大。比如在只有0和1的兩個字符的字符集，BM和SUNDAY和BF算法可能區(qū)別不大。模式串越短，壞字符不在模式串的可能性越大，構(gòu)造時間越短。所以BM和SUNDAY算法在大字符集的情況下進行搜詞的效率會高。
一般情況下，BM會比SUNDAY更優(yōu)，因為BM是做壞字符加好后綴這一段字符的對齊，對齊機率比較低，模式串相對目標(biāo)串移動快；而SUNDAY是做一個字符的對齊，對齊機率高，模式串相對目標(biāo)串移動慢。
