以下為學(xué)習(xí) 《數(shù)據(jù)結(jié)構(gòu)與算法之美 -- 字符串匹配》 的記錄言缤。
BF算法
即暴力匹配算法焦匈，循環(huán)遍歷匹配德绿。
RK算法
即根據(jù)哈希值進(jìn)行匹配岔帽。假設(shè)主串長(zhǎng)度為 m 玫鸟，模式串長(zhǎng)度為 n ，則只需計(jì)算主串中 m-n+1 個(gè)子串的哈希值山卦，然后與模式串的哈希值相比即可鞋邑。
哈希算法可以自定義。
比如使用字符集的個(gè)數(shù)作為幾進(jìn)制账蓉，然后將其轉(zhuǎn)換成整數(shù)枚碗。
如果字符中只包含 a-z， 那么字符集的個(gè)數(shù)為 26 铸本。則轉(zhuǎn)換成 26 進(jìn)制肮雨。
"aab" => ('a' - 'a') * 26 * 26 + ('a' - 'a') * 26 + ('b' - 'a') * 1
當(dāng)有哈希沖突時(shí)，即當(dāng)遇到不同的子串有相同哈希值時(shí)箱玷，再次與模式串的字符逐個(gè)比較是否相等怨规。
BM算法
從后向前匹配陌宿，效率比經(jīng)典的 KMP 算法還要快 3~4 倍。
壞字符規(guī)則
當(dāng)遇到不匹配的字符（稱之為壞字符）波丰，在模式串中的下標(biāo)為 si 壳坪。
- 如果模式串中該字符不存在，則直接向后移動(dòng)一個(gè)模式串的長(zhǎng)度掰烟。
- 如果存在爽蝴，下標(biāo)為 xi , 則移動(dòng) (si-xi) 位，使其跟主串的壞字符對(duì)應(yīng)纫骑。
移動(dòng)后蝎亚，繼續(xù)從模式串末尾開(kāi)始匹配。
記錄模式串中每個(gè)字符對(duì)應(yīng)的 index 先馆，重復(fù)的會(huì)被靠后的位置替代发框。
好后綴規(guī)則
當(dāng)遇到不匹配的字符，將已經(jīng)匹配過(guò)的字符（稱之為好后綴）煤墙。
- 在模式串中查找是否能匹配整個(gè)好后綴梅惯，如有，則移動(dòng)至對(duì)齊番捂。
- 若沒(méi)有个唧，則在模式串中查找是否有
前綴子串跟好后綴的后綴子串匹配，若有设预，則移動(dòng)最長(zhǎng)的前綴子串與其對(duì)應(yīng)。若沒(méi)有犁河，則直接移動(dòng)整個(gè)模式串鳖枕。
- 后綴子串，最后一個(gè)字符跟其對(duì)齊桨螺，不包括首字符宾符。abc，后綴子串為c灭翔，bc魏烫。
- 前綴子串，第一個(gè)字符跟其對(duì)齊肝箱，不包括末尾哄褒。abc，前綴子串為a煌张，ab呐赡。
求好后綴的匹配串的位置
記錄 suffix[k] = i ，k 表示后綴長(zhǎng)度骏融。subffix[1] = 1链嘀，表示最后一個(gè)字符在i=1開(kāi)始是匹配的萌狂。如果不存在，則 suffix[k] = -1 怀泊。
比如字符串 "dacda", suffix 數(shù)組如下茫藏。
suffix[1] = 1
suffix[2] = 0
suffix[3] = -1
suffix[4] = -1
由于還需要判斷是否有前綴子串與后綴的后綴子串匹配，所以還需記錄是否有前綴子串霹琼，prefix[k] = 0刷允，表示末尾 k 位數(shù)，有匹配的前綴子串碧囊。若為 -1 树灶，則沒(méi)有。
根據(jù) suffix 數(shù)組糯而，如果其值為 0天通，則表示有前綴子串。
prefix[1] = false
prefix[2] = true
prefix[3] = false
prefix[4] = false
suffix 數(shù)組計(jì)算方法：
模式串中的 0-i(0<=i<m-1) 子串與整個(gè)模式串求公共后綴熄驼。如果有多個(gè)像寒，保存最靠后的位置。
代碼如下：
// pattern-模式串瓜贾，m-模式串長(zhǎng)度诺祸。
var j = 0
while j < m - 1 {
var i = j
var k = 0
// 求公共后綴，從末尾比較
while i >= 0, pattern[m - k - 1] == pattern[i] {
k += 1
suffix[k] = i
i -= 1
}
if i == -1 {
prefix[k] = true
}
j += 1
}
壞字符規(guī)則與好后綴規(guī)則結(jié)合
取移動(dòng)步數(shù)最大的祭芦。
完整算法：
// p-模式串筷笨，m-模式串長(zhǎng)度，s-主串龟劲，n-主串長(zhǎng)度
function bm() {
var i = 0
while i <= n - m {
var j = m -1
while j >= 0 {
if s[i+j] != p[j] {
break;
}
j -= 1
}
if j < 0 {
return i
}
// j是壞字符
let x = j - bc[p[j]]
var y = 0
// 有好后綴
if j < m - 1 {
// 求y
y = getGoodSuffix(j)
}
step = max(x,y)
i += step
}
return -1
}
function getGoodSuffix(_ j: Int) -> Int {
// 壞字符后面一個(gè)j+1胃夏，后綴長(zhǎng)度為m-()
let k = m - 1 - j
if suffix[k] != -1 {
return j + 1 - suffix[k]
}
// 遍歷所有后綴子串
var r = m + 2
while r <= m - 1 {
if prefix[r] {
return r
}
r += 1
}
}
KMP算法
從前往后匹配。
當(dāng)遇到不匹配的字符時(shí)昌跌，下標(biāo)為j仰禀，查找前面匹配的字符串的前綴與后綴匹配的最大長(zhǎng)度值 k = next[j - 1] ，然后模式串 j = k 蚕愤。
即前 m 個(gè)字符答恶，前綴與后綴匹配的最大長(zhǎng)度為 k 。記為 next[m-1] = k 萍诱。
計(jì)算 next 數(shù)組悬嗓，采用動(dòng)態(tài)規(guī)劃。
假設(shè) next[i] = k, 若 pattern[i+1] = patter[k], 則 next[i+1] = k+1 ;
若不相等砂沛，則從 next[k-1] 再開(kāi)始計(jì)算烫扼。
// 模式串：pattern[]，n：模式串長(zhǎng)度
var i = 0
var j = 1
var k = 0
next=[0]
while j < n {
if patter[j] == patter[i] {
next[j] = ++k
j += 1
i += 1
} else {
let l = next[k - 1]
if l > 0 {
i = l
k = l
} else {
next[j] = 0
j += 1
}
}
}
代碼：
// m-主串長(zhǎng)度碍庵，n-模式串長(zhǎng)度
var i = 0
var j = 0
while i < m {
if s[i] == pattern[j] {
j += 1
i += 1
// 匹配完成
if j == n {
return i - j
}
} else {
if i < m {
if j >= 1 {
j = next[j - 1]
} else {
i += 1
}
}
}
}
return -1
