Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之字符串暴力匹配

更新時間：2022年02月18日 09:24:13 作者：我是小白呀

字符串暴力匹配算法是指在一個長字符串中暴力尋找是否包含某一子串所謂暴力匹配，就是不使用任何其他算法，將兩個字符串中的字符一一進行比對

概述

從今天開始, 小白我將帶大家開啟 Java 數(shù)據(jù)結(jié)構(gòu) & 算法的新篇章.

字符串匹配

字符串匹配 (String Matching) 指的是判斷一個字符串是否包含另一個字符串.

舉個例子:

字符串 “Hello World” 包含字符串 “Hello”
字符串 “Hello World” 不包含字符串 “LaLaLa”

暴力匹配

暴力匹配 (Brute-Force) 的思路:

如果charArray1[i] == charArray2[j], 即匹配成功, i++, j++, 繼續(xù)匹配下一個字符
如果匹配失敗, i 重置為i - (j - 1), j 重置成 0, 繼續(xù)暴力匹配

暴力匹配實現(xiàn)

public class 暴力匹配 {

    public static int BruteForce(String str1, String str2) {

        // 將字符串轉(zhuǎn)化為char數(shù)組
        char[] charArray1 = str1.toCharArray();
        char[] charArray2 = str2.toCharArray();

        // string長度
        int length1 = charArray1.length;
        int length2 = charArray2.length;

        // 調(diào)試輸出
        System.out.println(charArray1);
        System.out.println(charArray2);

        int i = 0;
        int j = 0;

        while (i < length1 && j < length2) {

            // 判斷是否匹配
            if (charArray1[i] == charArray2[j]) {

                // 各往后挪一位
                i++;
                j++;
            } else {

                // 重新匹配
                i = i - (j - 1);
                j = 0;
            }
        }

        // 匹配完成, 返回index
        if (j == length2) {
            return i - j;
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {

        // 字符串1
        String str1 = "I am little white";

        // 字符串2
        String str2 = "white";

        // 暴力匹配
        int result = BruteForce(str1, str2);
        System.out.println(result);
    }
}

輸出結(jié)果: