說起“字符串匹配”，恐怕算得上是計算機領域應用最多的功能之一，為了滿足這一需求，聰明的計算機科學家們發明了許多巧妙的算法。在上一篇漫畫中，我們介紹了BF算法和RK算法，沒看過的小伙伴可以先補補...
說起“字符串匹配”，恐怕算得上是計算機領域應用最多的功能之一，為了滿足這一需求，聰明的計算機科學家們發明了許多巧妙的算法。
在上一篇漫畫中，我們介紹了BF算法和RK算法，沒看過的小伙伴可以先補補課：
漫畫：什么是字符串匹配算法？
今天，我們來介紹一種性能大大優化的字符串匹配算法。
BF算法是如何工作的？
正如同它的全稱BruteForce一樣，BF算法使用簡單粗暴的方式，對主串和模式串進行逐個字符的比較。
比如給定主串和模式串如下：
它們的比較過程是什么樣的呢？
第一輪，模式串和主串的第一個等長子串比較，發現第0位字符一致，第1位字符一致，第2位字符不一致：
第二輪，模式串向后挪動一位，和主串的第二個等長子串比較，發現第0位字符不一致：
第三輪，模式串繼續向后挪動一位，和主串的第三個等長子串比較，發現第0位字符不一致：
以此類推，一直到第N輪：
當模式串挪動到某個合適位置，逐個字符比較，發現每一位字符都是匹配時，比較結束：
壞字符規則
“壞字符” 是什么意思？就是指模式串和子串當中不匹配的字符。
還以上面的字符串為例，當模式串和主串的第一個等長子串比較時，子串的最后一個字符T就是壞字符：
當檢測到第一個壞字符之后，我們有必要讓模式串一位一位向后挪動和比較嗎？并不需要。
因為只有模式串與壞字符T對齊的位置也是字符T的情況下，兩者才有匹配的可能。
不難發現，模式串的第1位字符也是T，這樣一來我們就可以對模式串做一次“乾坤大挪移”，直接把模式串當中的字符T和主串的壞字符對齊，進行下一輪的比較：
壞字符的位置越靠右，下一輪模式串的挪動跨度就可能越長，節省的比較次數也就越多。這就是BM算法從右向左檢測的好處。
接下來，我們繼續逐個字符比較，發現右側的G、C、G都是一致的，但主串當中的字符A，是又一個壞字符：
我們按照剛才的方式，找到模式串的第2位字符也是A，于是我們把模式串的字符A和主串中的壞字符對齊，進行下一輪比較：
接下來，我們繼續逐個字符比較，這次發現全部字符都是匹配的，比較公正完成：
//在模式串中，查找index下標之前的字符是否和壞字符匹配
private
static
int
findCharacter
(
String
pattern
,
char
badCharacter
,
int
index
)
{
for
(
int
i
=
index
-
1
;
i
>=
0
;
i
--){
if
(
pattern
.
charAt
(
i
)
==
badCharacter
){
return
i
;
}
}
//模式串不存在該字符，返回-1
return
-
1
;
}
public
static
int
boyerMoore
(
String
str
,
String
pattern
)
{
int
strLength
=
str
.
length
();
int
patternLength
=
pattern
.
length
();
//模式串的起始位置
int
start
=
0
;
while
(
start
<=
strLength
-
patternLength
)
{
int
i
;
//從后向前，逐個字符比較
for
(
i
=
patternLength
-
1
;
i
>=
0
;
i
--)
{
if
(
str
.
charAt
(
start
+
i
)
!=
pattern
.
charAt
(
i
))
//發現壞字符，跳出比較，i記錄了壞字符的位置
break
;
}
if
(
i
<
0
)
{
//匹配成功，返回第一次匹配的下標位置
return
start
;
}
//尋找壞字符在模式串中的對應
int
charIndex
=
findCharacter
(
pattern
,
str
.
charAt
(
start
+
i
),
i
);
//計算壞字符產生的位移
int
bcOffset
=
charIndex
>=
0
?
i
-
charIndex
:
i
+
1
;
start
+=
bcOffset
;
}
return
-
1
;
}
public
static
void
main
(
String
[]
args
)
{
String
str
=
"GTTATAGCTGGTAGCGGCGAA"
;
String
pattern
=
"GTAGCGGCG"
;
int
index
=
boyerMoore
(
str
,
pattern
);
System
.
out
.
println
(
"首次出現位置："
+
index
);
}
好后綴規則
“好后綴” 又是什么意思？就是指模式串和子串當中相匹配的后綴。
讓我們看一組新的例子：
對于上面的例子，如何我們繼續使用“壞字符規則”，會有怎樣的效果呢？
從后向前比對字符，我們發現后面三個字符都是匹配的，到了第四個字符的時候，發現壞字符G：
接下來我們在模式串找到了對應的字符G，但是按照壞字符規則，模式串僅僅能夠向后挪動一位：
這時候壞字符規則顯然并沒有起到作用，為了能真正減少比較次數，輪到我們的好后綴規則出場了。由于好后綴規則的實現細節比壞字符規則要難理解得多，所以我們這里只介紹一個大概思路：
我們回到第一輪的比較過程，發現主串和模式串都有共同的后綴“GCG”，這就是所謂的“好后綴”。
如果模式串其他位置也包含與“GCG”相同的片段，那么我們就可以挪動模式串，讓這個片段和好后綴對齊，進行下一輪的比較：
顯然，在這個例子中，采用好后綴規則能夠讓模式串向后移動更多位，節省了更多無謂的比較。
來源：本文內容搜集或轉自各大網絡平臺，并已注明來源、出處，如果轉載侵犯您的版權或非授權發布，請聯系小編，我們會及時審核處理。
聲明：江蘇教育黃頁對文中觀點保持中立，對所包含內容的準確性、可靠性或者完整性不提供任何明示或暗示的保證，不對文章觀點負責，僅作分享之用，文章版權及插圖屬于原作者。
聯系郵箱：service#改成@jsedu114.com
地 址：中國●江蘇
南京市秦淮區洪武路359號1506室
Copyright©2013-2025 ?JSedu114 All Rights Reserved. 江蘇教育信息綜合發布查詢平臺保留所有權利
蘇公網安備32010402000125
蘇ICP備14051488號-3技術支持：南京博盛藍睿網絡科技有限公司
南京思必達教育科技有限公司版權所有 百度統計
新浪微博
公眾微信
最新文章
