說起“字符串匹配”，恐怕算得上是計(jì)算機(jī)領(lǐng)域應(yīng)用最多的功能之一，為了滿足這一需求，聰明的計(jì)算機(jī)科學(xué)家們發(fā)明了許多巧妙的算法。

在上一篇漫畫中，我們介紹了BF算法和RK算法，沒看過的小伙伴可以先補(bǔ)補(bǔ)課：

漫畫：什么是字符串匹配算法？

今天，我們來介紹一種性能大大優(yōu)化的字符串匹配算法。

BF算法是如何工作的？

正如同它的全稱BruteForce一樣，BF算法使用簡(jiǎn)單粗暴的方式，對(duì)主串和模式串進(jìn)行逐個(gè)字符的比較。

比如給定主串和模式串如下：

它們的比較過程是什么樣的呢？

第一輪，模式串和主串的第一個(gè)等長子串比較，發(fā)現(xiàn)第0位字符一致，第1位字符一致，第2位字符不一致：

第二輪，模式串向后挪動(dòng)一位，和主串的第二個(gè)等長子串比較，發(fā)現(xiàn)第0位字符不一致：

第三輪，模式串繼續(xù)向后挪動(dòng)一位，和主串的第三個(gè)等長子串比較，發(fā)現(xiàn)第0位字符不一致：

以此類推，一直到第N輪：

當(dāng)模式串挪動(dòng)到某個(gè)合適位置，逐個(gè)字符比較，發(fā)現(xiàn)每一位字符都是匹配時(shí)，比較結(jié)束：

壞字符規(guī)則

“壞字符” 是什么意思？就是指模式串和子串當(dāng)中不匹配的字符。

還以上面的字符串為例，當(dāng)模式串和主串的第一個(gè)等長子串比較時(shí)，子串的最后一個(gè)字符T就是壞字符：

當(dāng)檢測(cè)到第一個(gè)壞字符之后，我們有必要讓模式串一位一位向后挪動(dòng)和比較嗎？并不需要。

因?yàn)橹挥?strong>模式串與壞字符T對(duì)齊的位置也是字符T的情況下，兩者才有匹配的可能。

不難發(fā)現(xiàn)，模式串的第1位字符也是T，這樣一來我們就可以對(duì)模式串做一次“乾坤大挪移”，直接把模式串當(dāng)中的字符T和主串的壞字符對(duì)齊，進(jìn)行下一輪的比較：

壞字符的位置越靠右，下一輪模式串的挪動(dòng)跨度就可能越長，節(jié)省的比較次數(shù)也就越多。這就是BM算法從右向左檢測(cè)的好處。

接下來，我們繼續(xù)逐個(gè)字符比較，發(fā)現(xiàn)右側(cè)的G、C、G都是一致的，但主串當(dāng)中的字符A，是又一個(gè)壞字符：

我們按照剛才的方式，找到模式串的第2位字符也是A，于是我們把模式串的字符A和主串中的壞字符對(duì)齊，進(jìn)行下一輪比較：

接下來，我們繼續(xù)逐個(gè)字符比較，這次發(fā)現(xiàn)全部字符都是匹配的，比較公正完成：

1. //在模式串中，查找index下標(biāo)之前的字符是否和壞字符匹配

2. private

4. static

6. int

7. findCharacter

8. (

9. String

10. pattern

11. ,

13. char

14. badCharacter

15. ,

17. int

18. index

19. )

21. {

23. for

24. (

25. int

26. i

27. =

28. index

29. -

30. 1

31. ;

32. i

33. >=

34. 0

35. ;

36. i

37. --){

39. if

40. (

41. pattern

42. .

43. charAt

44. (

45. i

46. )

48. ==

49. badCharacter

50. ){

52. return

53. i

54. ;

56. }

58. }

60. //模式串不存在該字符，返回-1

62. return

64. -

65. 1

66. ;

67. }

68. public

70. static

72. int

73. boyerMoore

74. (

75. String

76. str

77. ,

79. String

80. pattern

81. )

83. {

85. int

86. strLength

87. =

88. str

89. .

90. length

91. ();

93. int

94. patternLength

95. =

96. pattern

97. .

98. length

99. ();

101. //模式串的起始位置

103. int

104. start

105. =

107. 0

108. ;

110. while

112. (

113. start

114. <=

115. strLength

116. -

117. patternLength

118. )

120. {

122. int

123. i

124. ;

126. //從后向前，逐個(gè)字符比較

128. for

130. (

131. i

132. =

133. patternLength

134. -

136. 1

137. ;

138. i

139. >=

141. 0

142. ;

143. i

144. --)

146. {

148. if

150. (

151. str

152. .

153. charAt

154. (

155. start

156. +

157. i

158. )

160. !=

161. pattern

162. .

163. charAt

164. (

165. i

166. ))

168. //發(fā)現(xiàn)壞字符，跳出比較，i記錄了壞字符的位置

170. break

171. ;

173. }

175. if

177. (

178. i

179. <

181. 0

182. )

184. {

186. //匹配成功，返回第一次匹配的下標(biāo)位置

188. return

189. start

190. ;

192. }

194. //尋找壞字符在模式串中的對(duì)應(yīng)

196. int

197. charIndex

198. =

199. findCharacter

200. (

201. pattern

202. ,

203. str

204. .

205. charAt

206. (

207. start

208. +

209. i

210. ),

211. i

212. );

214. //計(jì)算壞字符產(chǎn)生的位移

216. int

217. bcOffset

218. =

219. charIndex

220. >=

221. 0

223. ?

224. i

225. -

226. charIndex

227. :

228. i

229. +

230. 1

231. ;

232. start

233. +=

234. bcOffset

235. ;

237. }

239. return

241. -

242. 1

243. ;

244. }

245. public

247. static

249. void

250. main

251. (

252. String

253. []

254. args

255. )

257. {

259. String

260. str

261. =

263. "GTTATAGCTGGTAGCGGCGAA"

264. ;

266. String

267. pattern

268. =

270. "GTAGCGGCG"

271. ;

273. int

274. index

275. =

276. boyerMoore

277. (

278. str

279. ,

280. pattern

281. );

283. System

284. .

285. out

286. .

287. println

288. (

289. "首次出現(xiàn)位置："

291. +

292. index

293. );

294. }

好后綴規(guī)則

“好后綴” 又是什么意思？就是指模式串和子串當(dāng)中相匹配的后綴。

讓我們看一組新的例子：

對(duì)于上面的例子，如何我們繼續(xù)使用“壞字符規(guī)則”，會(huì)有怎樣的效果呢？

從后向前比對(duì)字符，我們發(fā)現(xiàn)后面三個(gè)字符都是匹配的，到了第四個(gè)字符的時(shí)候，發(fā)現(xiàn)壞字符G：

接下來我們?cè)谀Ｊ酱业搅藢?duì)應(yīng)的字符G，但是按照壞字符規(guī)則，模式串僅僅能夠向后挪動(dòng)一位：

這時(shí)候壞字符規(guī)則顯然并沒有起到作用，為了能真正減少比較次數(shù)，輪到我們的好后綴規(guī)則出場(chǎng)了。由于好后綴規(guī)則的實(shí)現(xiàn)細(xì)節(jié)比壞字符規(guī)則要難理解得多，所以我們這里只介紹一個(gè)大概思路：

我們回到第一輪的比較過程，發(fā)現(xiàn)主串和模式串都有共同的后綴“GCG”，這就是所謂的“好后綴”。

如果模式串其他位置也包含與“GCG”相同的片段，那么我們就可以挪動(dòng)模式串，讓這個(gè)片段和好后綴對(duì)齊，進(jìn)行下一輪的比較：

顯然，在這個(gè)例子中，采用好后綴規(guī)則能夠讓模式串向后移動(dòng)更多位，節(jié)省了更多無謂的比較。