说起“字符串匹配”，恐怕算得上是计算机领域应用最多的功能之一，为了满足这一需求，聪明的计算机科学家们发明了许多巧妙的算法。

在上一篇漫画中，我们介绍了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和主串中的坏字符对齐，进行下一轮比较：

接下来，我们继续逐个字符比较，这次发现全部字符都是匹配的，比较公正完成：

1. //在模式串中，查找index下标之前的字符是否和坏字符匹配

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. //从后向前，逐个字符比较

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. //发现坏字符，跳出比较，i记录了坏字符的位置

170. break

171. ;

173. }

175. if

177. (

178. i

179. <

181. 0

182. )

184. {

186. //匹配成功，返回第一次匹配的下标位置

188. return

189. start

190. ;

192. }

194. //寻找坏字符在模式串中的对应

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. //计算坏字符产生的位移

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. "首次出现位置："

291. +

292. index

293. );

294. }

好后缀规则

“好后缀” 又是什么意思？就是指模式串和子串当中相匹配的后缀。

让我们看一组新的例子：

对于上面的例子，如何我们继续使用“坏字符规则”，会有怎样的效果呢？

从后向前比对字符，我们发现后面三个字符都是匹配的，到了第四个字符的时候，发现坏字符G：

接下来我们在模式串找到了对应的字符G，但是按照坏字符规则，模式串仅仅能够向后挪动一位：

这时候坏字符规则显然并没有起到作用，为了能真正减少比较次数，轮到我们的好后缀规则出场了。由于好后缀规则的实现细节比坏字符规则要难理解得多，所以我们这里只介绍一个大概思路：

我们回到第一轮的比较过程，发现主串和模式串都有共同的后缀“GCG”，这就是所谓的“好后缀”。

如果模式串其他位置也包含与“GCG”相同的片段，那么我们就可以挪动模式串，让这个片段和好后缀对齐，进行下一轮的比较：

显然，在这个例子中，采用好后缀规则能够让模式串向后移动更多位，节省了更多无谓的比较。