BF algorithm

BF algorithm, short for brute force algorithm. Used to detect whether a string is a substring of another string.

Concept of substring

Suppose the string x = 'girlfriend', y = 'friend', then y is the substring of X. Similarly, end is a substring of friend.

Idea of BF algorithm

The idea of BF algorithm is very simple and rough, which is a little matching from front to back. For example, the substring x = ABCD | the main string is y = abdabceabcde. If x [0] = y [0] continues to compare x [1] y [1], if it continues until x [3] = y [3], the whole string of X matches. If x [0] = y [0] continues to compare x [1] and Y [i] find inequality, start comparing y [1] with x [0], and then continue x [1] and Y [2].

First step

abdabceabcde
abcd

When we get to the third position, it's d above and C below, so we start the second part.

Step 2

abdabceabcde
-abcd

Step 3

abdabceabcde
--abcd

Step 4

abdabceabcde
---abcd

... until the 7th position of the main string (counting from 0) finally matches.

Java code implementation

public class BruteForce {

    public static void main(String[] args) {
        System.out.println(isSubstring("abdabceabcde","abcd")); // true
        System.out.println(isSubstring("abdabceabcde","ff"));   // false
    }

    private static boolean isSubstring(String main,String sub){
        if(main == null || sub == null) {
            return false;
        }
        if(main.length() < sub.length()) { // 主串要长于子串
            return false;
        }
        if(main.equals(sub)) { // 主串，子串 相等的情况
            return true;
        }
        int len = main.length() - sub.length();
        for (int i = 0; i < len; i++) {
            boolean match = true;
            for (int j = 0; j < sub.length(); j++) {
                if(main.charAt(i+j) != sub.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if(match) {
                return true;
            }
        }
        return false;
    }

}