Java 算法篇-深入了解 BF 与 KMP 算法

在Java中，BF（Brute Force）算法和KMP算法是用于字符串匹配的两种常见算法。

BF算法的核心思想是遍历主字符串，对每个字符开始向后比对是否与模式字符串匹配。

KMP算法的核心思想是通过一个next数组预处理模式字符串，当出现字符不匹配时，可以知道模式字符串中的哪些部分已经与主字符串匹配，可以直接跳过这些部分，从另一个位置开始比对。

以下是Java中实现这两种算法的示例代码：

// BF算法
public class BruteForce {
    public static int search(String txt, String pat) {
        int M = pat.length();
        int N = txt.length();
        for (int i = 0; i <= N - M; i++) {
            int j;
            for (j = 0; j < M; j++) {
                if (pat.charAt(j) != txt.charAt(i + j))
                    break;
            }
            if (j == M)
                return i;
        }
        return -1;
    }
}
 
// KMP算法
public class KMP {
    private int[] computePrefixFunction(String key) {
        int M = key.length();
        int[] prefix = new int[M];
        int j = 0;
        for (int i = 1; i < M; i++) {
            while (j > 0 && key.charAt(i) != key.charAt(j)) {
                j = prefix[j - 1];
            }
            if (key.charAt(i) == key.charAt(j)) {
                j++;
            }
            prefix[i] = j;
        }
        return prefix;
    }
 
    public int search(String txt, String pat) {
        int M = pat.length();
        int N = txt.length();
        int[] prefix = computePrefixFunction(pat);
        int j = 0;
        for (int i = 0; i < N; i++) {
            while (j > 0 && pat.charAt(j) != txt.charAt(i)) {
                j = prefix[j - 1];
            }
            if (pat.charAt(j) == txt.charAt(i)) {
                j++;
            }
            if (j == M) {
                return (i - M + 1);
            }
        }
        return -1;
    }
}

在这两个类中，search方法分别实现了BF和KMP算法来在主字符串txt中查找模式字符串pat的位置。如果找到，返回模式字符串在主字符串中的起始位置，如果未找到，返回-1。computePrefixFunction是KMP算法中用于计算模式字符串的next数组的辅助方法。