BF算法 串模式匹配算法 C语言解说
发布时间：2022-07-07 23:20:56 所属栏目：语言 来源：互联网
导读：串的模式匹配算法，通俗地理解，是一种用来判断两个串之间是否具有主串与子串关系的算法。 主串与子串：如果串 A（如 shujujiegou）中包含有串 B（如 ju），则称串 A 为主串，串 B 为子串。主串与子串之间的关系可简单理解为一个串 包含 另一个串的关系。 实
|
串的模式匹配算法，通俗地理解，是一种用来判断两个串之间是否具有"主串与子串"关系的算法。 主串与子串：如果串 A（如 "shujujiegou"）中包含有串 B（如 "ju"），则称串 A 为主串，串 B 为子串。主串与子串之间的关系可简单理解为一个串 "包含" 另一个串的关系。 实现串的模式匹配的算法主要有以下两种： 普通的模式匹配算法； 快速模式匹配算法； 本节，先来学习普通模式匹配（BF）算法的实现。 BF算法原理 普通模式匹配算法，其实现过程没有任何技巧，就是简单粗暴地拿一个串同另一个串中的字符一一比对，得到最终结果。 由此，串 A 与串 B 以供经历了 6 次匹配的过程才成功，通过整个模式匹配的过程，证明了串 A 是串 B 的子串（串 B 是串 A 的主串）。 接下来，我们要编写代码实现两个串的模式匹配（图 1 ~图 4）。 BF算法实现 BF 算法的实现思想是：将用户指定的两个串 A 和串 B，使用串的定长顺序存储结构存储起来，然后循环实现两个串的模式匹配过程，C 语言实现代码如下： #include <stdio.h> #include <string.h> //串普通模式匹配算法的实现函数，其中 B是伪主串，A是伪子串 int mate(char * B,char *A){ int i=0,j=0; while (i<strlen(B) && j<strlen(A)) { if (B[i]==A[j]) { i++; j++; }else{ i=i-j+1; j=0; } } //跳出循环有两种可能，i=strlen(B)说明已经遍历完主串，匹配失败；j=strlen(A),说明子串遍历完成，在主串中成功匹配 if (j==strlen(A)) { return i-strlen(A)+1; } //运行到此，为i==strlen(B)的情况 return 0; } int main() { int number=mate("ababcabcacbab", "abcac"); printf("%d",number); return 0; } 程序运行结果： 6 注意，在实现过程中，我们借助 i-strlen(A)+1 就可以得到成功模式匹配所用的次数，也就是串 A 移动的总次数。 BF算法时间复杂度 该算法最理想的时间复杂度 O(n)，n 表示串 A 的长度，即第一次匹配就成功。 BF 算法最坏情况的时间复杂度为 O(n*m)，n 为串 A 的长度，m 为串 B 的长度。例如，串 B 为 "0000000001"，而串 A 为 "01"，这种情况下，两个串每次匹配，都必须匹配至串 A 的最末尾才能判断匹配失败，因此运行了 n*m 次。 （编辑：航空爱好网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐