串的模式比對算法——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)。