字元串比對算法--BF算法

BF（ Brute force）算法，又稱暴力搜尋。

思想：首先将原字元串和要比對的字元串（以下簡稱子串）左端對齊，之後比較第一個字元相同則繼續比較第二個字元,直至全部比對；如果不同将子串向後移動一位再繼續比較。如圖所示：

JAVA實作demo：

class BF
{
    String total_string;
    String sub_string;
    public BF(String a,String b)
    {
       total_string=a;
       sub_string=b;

    }
    public int find()
    {
        int i;      
        for(i=;i<=total_string.length()-sub_string.length();i++)
        {
            int j=;
            int q=i;
            while(total_string.substring(q,q+).equals(sub_string.substring(j,j+)))
            {
                j++;
                q++;
                if(j==sub_string.length()-)
                    return i;
            } 
        }
        return -;
    }
    public static void main(String[] args)
    {
       BF b=new BF("ABCDEF","DEF");
       System.out.println(b.find());
    }
}
           

時間複雜度為O(MN),M代表長串的長度，N代表子串的長度。