hosteons中文网

串的模式匹配算法，通俗地理解，是一种用来判断两个串之间是否具有"主串与子串"关系的算法。

主串与子串：如果串 A（如 "shujujiegou"）中包含有串 B（如 "ju"），则称串 A 为主串，串 B 为子串。主串与子串之间的关系可简单理解为一个串 "包含" 另一个串的关系。

实现串的模式匹配的算法主要有以下两种：

1. 普通的模式匹配算法；
2. 快速模式匹配算法；

本节，先来学习普通模式匹配（BF）算法的实现。

BF算法原理

普通模式匹配算法，其实现过程没有任何技巧，就是简单粗暴地拿一个串同另一个串中的字符一一比对，得到最终结果。

例如，使用普通模式匹配算法判断串 A（"abcac"）是否为串 B（"ababcabacabab"）子串的判断过程如下：

首先，将串 A 与串 B 的首字符对齐，然后逐个判断相对的字符是否相等，如图 1 所示：

图 1 串的第一次模式匹配示意图