BF算法(串模式匹配算法)C语言详解
串的模式匹配算法,通俗地理解,是一种用来判断两个串之间是否具有"主串与子串"关系的算法。
主串与子串:如果串 A(如 "shujujiegou")中包含有串 B(如 "ju"),则称串 A 为主串,串 B 为子串。主串与子串之间的关系可简单理解为一个串 "包含" 另一个串的关系。
实现串的模式匹配的算法主要有以下两种:
- 普通的模式匹配算法;
- 快速模式匹配算法;
本节,先来学习普通模式匹配(BF)算法的实现。
BF算法原理
普通模式匹配算法,其实现过程没有任何技巧,就是简单粗暴地拿一个串同另一个串中的字符一一比对,得到最终结果。
例如,使用普通模式匹配算法判断串 A("abcac")是否为串 B("ababcabacabab")子串的判断过程如下:
首先,将串 A 与串 B 的首字符对齐,然后逐个判断相对的字符是否相等,如图 1 所示: