串的模式匹配算法——BF算法

 在主串中，从指定的起始位置pos开始，用i和j分别指示主串S和模式T中正待比较的字符位置，i的初值为pos，j的初值为1。

i与j所指示的字符比较，若相等，则i与j指示的位置同时后移，比较下一对字符。若不等，从主串的下一个字符（i=i-j+2）开始重新和模式T的第一个字符（j=1）比较。

若j大于模式T的长度，则说明匹配成功，返回 和模式T的第一个字符相等的字符 在主串S中的序号（i-T.length）。否则匹配失败。

1 public class BF {
 2     public  static void main(String[] args) {
 3         String S="ababcabcacbab";
 4         String T="abcac";
 5         char[] charS=S.toCharArray();
 6         char[] charT=T.toCharArray();
 7         int pos=1;
 8         run(charS,charT,pos);
 9     }
10     public static void run(char[] charS,char[] charT,int pos) {
11         int i=pos;
12         int j=1;
13         while(i<=charS.length && j<=charT.length) 
14         {
15             if(charS[i-1] == charT[j-1]) 
16             {
17                 ++i;
18                 ++j;
19             }else 
20             {
21                 i=i-j+2;
22                 j=1;
23             }
24         }
25         if(j>charT.length) 
26         {
27             System.out.println("匹配成功,序号为"+(i-charT.length));
28         }else
29         {
30             System.out.println("匹配失败");
31         }
32     }
33 }      

 BF算法在最坏的条件下时间复杂度为O(m×n)。