（点击上方公众号，可快速关注）
字符串匹配，在实际编程中经常遇到。其相应的算法有很多，本文就BF算法和KMP算法，谈一下自己的理解。并结合平时编程，修改了一下，使其更符合我们的使用习惯。（注：标准BF算法和KMP算法，为研究方便，其字符数组[0]存放的都是字符串的长度。本文讲解中，并没有保存字符串长度。后面给出的示例代码中，字符数组中是否保存有字符串长度，都给出了相应的算法代码。） 一、BF 算法 (Brute Force): BF算法核心思想是：首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则T向右移动一个字符的位置，再依次进行比较。如果存在k，1≤k≤N，且S[k 1…k M]=T[1…M]，则匹配成功；否则失败。该算法最坏情况下要进行M*(N-M 1)次比较，时间复杂度为O(M*N)。下面结合图片，解释一下： S代表源字符串，T代表我们要查找的字符串。BF算法可以表述如下：依次遍历字符串S，看是否字符串S中含有字符串T。因此，我们依次比较S[0] 和T[0]、S[1] 和T[1]、S[2] 和T[2]……S[n]和T[n] ，从图中我们可知，S[0]-S[7]和T[0]-T[7]依次相等。当匹配到S[8]和T[8]时，两个字符不等。根据定义，此时S和T都要回溯，T向右移动一个字符的位置，即S回溯到S[1]的位置，T回溯到T[0]的位置，再重新开始比较。此时，S[1]和T[0]、S[2]和T[1]……如果再次发现不匹配字符，则再次回溯，即S回溯到S[2]的位置，T回到T[0]的位置。循环往复，直到到达S或者T字符串的结尾。如果是到达S串的结尾，则表示匹配失败，如果是到达T串的结尾，则表示匹配成功。 BF算法优点：思想简单，直接，无需对字符串S和T进行预处理。缺点：每次字符不匹配时，都要回溯到开始位置，时间开销大。 下面是BF算法的代码实现：bf.c
|
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
