首页 > 代码库 > BF字符串匹配算法

BF字符串匹配算法

Brute Force算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;

若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。

 

技术分享

 

代码示例:

技术分享
 1 <?php
 2     //BF算法
 3     /**
 4     * 从第pos的下标开始查询,匹配成功则返回下标,否则返回false
 5     */
 6     function bf($s, $t, $pos=0)
 7     {
 8         $i = $pos;
 9         $j = 0;
10         $slength = strlen($s);
11         $tlength = strlen($t);
12         while($i+$j<$slength && $j<$tlength)
13         {
14             if($s[$i+$j] == $t[$j])
15             {
16                 $j++;
17             } else {
18                 $j = 0;
19                 ++$i;
20             }
21         }
22         if($j>=$tlength)
23         {
24             return $i;
25         } else {
26             return false;
27         }
28     }
29     
30     $s = ‘ababcababa‘;
31     $t = ‘ababa‘;
32     
33     $res = bf($s,$t,0);
34     var_dump($res);
View Code

 

BF字符串匹配算法