JAVA代码实现对上述 3 个算法（BF算法、KMP 算法、BM 算法）进行时间复杂性分析,并设计实验程序验证分析结果

下面是对三个算法的时间复杂性分析和实验程序设计：

1. BF算法：

时间复杂度：O(n*m)，其中n为文本串的长度，m为模式串的长度。

实验程序设计：

public class BFMatch {
    public static void main(String[] args) {
        String text = "abababababababababababababababababababac";
        String pattern = "ababac";
        int index = bfMatch(text,pattern);
        System.out.println("匹配结果：" + index);
    }

    public static int bfMatch(String text, String pattern) {
        int tLen = text.length();
        int pLen = pattern.length();
        for (int i = 0; i <= tLen - pLen; i++) {
            int j;
            for (j = 0; j < pLen; j++) {
                if (text.charAt(i+j) != pattern.charAt(j)) {
                    break;
                }
            }
            if (j == pLen) {
                return i;
            }
        }
        return -1;
    }
}

2. KMP算法：

时间复杂度：O(n+m)，其中n为文本串的长度，m为模式串的长度。

实验程序设计：

public class KMPMatch {
    public static void main(String[] args) {
        String text = "abababababababababababababababababababac";
        String pattern = "ababac";
        int index = kmpMatch(text,pattern);
        System.out.println("匹配结果：" + index);
    }

    public static int kmpMatch(String text, String pattern) {
        int tLen = text.length();
        int pLen = pattern.length();
        int[] next = getNext(pattern);
        int i = 0, j = 0;
        while (i < tLen && j < pLen) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == pLen) {
            return i - j;
        } else {
            return -1;
        }
    }

    public static int[] getNext(String pattern) {
        int pLen = pattern.length();
        int[] next = new int[pLen];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < pLen - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }
}

3. BM算法：

时间复杂度：O(n/m)，其中n为文本串的长度，m为模式串的长度。

实验程序设计：

public class BMMatch {
    public static void main(String[] args) {
        String text = "abababababababababababababababababababac";
        String pattern = "ababac";
        int index = bmMatch(text,pattern);
        System.out.println("匹配结果：" + index);
    }

    public static int bmMatch(String text, String pattern) {
        int tLen = text.length();
        int pLen = pattern.length();
        int[] bmBc = preBmBc(pattern);
        int[] bmGs = preBmGs(pattern);
        int i = pLen - 1;
        while (i < tLen) {
            int j = pLen - 1;
            while (j >= 0 && text.charAt(i) == pattern.charAt(j)) {
                i--;
                j--;
            }
            if (j < 0) {
                return i + 1;
            }
            i += Math.max(bmBc[text.charAt(i)] - pLen + 1 + j, bmGs[j]);
        }
        return -1;
    }

    private static int[] preBmBc(String pattern) {
        int pLen = pattern.length();
        int[] bmBc = new int[256];
        Arrays.fill(bmBc, pLen);
        for (int i = 0; i < pLen - 1; i++) {
            bmBc[pattern.charAt(i)] = pLen - 1 - i;
        }
        return bmBc;
    }

    private static int[] preBmGs(String pattern) {
        int pLen = pattern.length();
        int[] bmGs = new int[pLen];
        int[] suffix = suffix(pattern);
        Arrays.fill(bmGs, pLen);
        for (int i = pLen - 1; i >= 0; i--) {
            if (suffix[i] == i + 1) {
                for (int j = 0; j < pLen - 1 - i; j++) {
                    if (bmGs[j] == pLen) {
                        bmGs[j] = pLen - 1 - i;
                    }
                }
            }
        }
        for (int i = 0; i < pLen - 1; i++) {
            bmGs[pLen - 1 - suffix[i]] = pLen - 1 - i;
        }
        return bmGs;
    }

    private static int[] suffix(String pattern) {
        int pLen = pattern.length();
        int[] suffix = new int[pLen];
        suffix[pLen - 1] = pLen;
        int i = pLen - 2, j = pLen - 1;
        while (i >= 0) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                i--;
                j--;
                suffix[i] = j + 1;
            } else {
                j = suffix[j];
                if (j <= i) {
                    j = i + 1;
                }
            }
        }
        return suffix;
    }
}