Java函数实现字符串匹配的基本算法

字符串匹配是计算机科学中一个重要的问题，指的是在一个主字符串中寻找一个模式字符串的出现位置。实现字符串匹配的基本算法有多种方法，下面将介绍三种常用的算法：暴力匹配、KMP算法和Boyer-Moore算法。

1. 暴力匹配算法（Brute-Force）

暴力匹配算法是最简单直观的方法，它的思路是从主字符串的每个位置开始，逐个比较模式字符串的字符是否匹配。如果匹配成功，继续比较下一个字符，如果不匹配，则将主字符串的指针向后移动一位。

public int indexOf(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text.charAt(i + j) != pattern.charAt(j)) {
                break;
            }
        }
        if (j == m) {
            return i;
        }
    }
    return -1;
}

该算法的时间复杂度是O(n * m)，其中n是主字符串的长度，m是模式字符串的长度。

2. KMP算法（Knuth-Morris-Pratt）

KMP算法是一种优化暴力匹配算法的字符串匹配算法。它利用模式字符串的部分匹配表来避免不必要的比较操作。首先，通过对模式字符串构建部分匹配表，计算出每个位置的最长相同前缀后缀的长度；然后，在匹配过程中，当出现不匹配时，根据部分匹配表可以直接跳过多个字符，将模式字符串向右移动。

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

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

KMP算法的时间复杂度是O(n + m)，其中n是主字符串的长度，m是模式字符串的长度。

3. Boyer-Moore算法

Boyer-Moore算法是一种更高效的字符串匹配算法，它利用模式字符串中的字符分布规律来进行匹配。它的核心思想是从主字符串的末尾开始，逐个将模式字符串与主字符串从后往前进行比较。当出现不匹配时，根据字符在模式字符串中的位置和Bad Character规则或Good Suffix规则，选择合适的移动方式，将模式字符串向右移动。

public int indexOf(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] badChar = buildBadChar(pattern);
    int[] suffix = buildSuffix(pattern);
    int i = m - 1, j = m - 1;
    while (i < n) {
        if (text.charAt(i) == pattern.charAt(j)) {
            if (j == 0) {
                return i;
            }
            i--;
            j--;
        } else {
            int x = badChar[text.charAt(i)];
            int y = suffix[j];
            i += Math.max(x, y);
            j = m - 1;
        }
    }
    return -1;
}

private int[] buildBadChar(String pattern) {
    int m = pattern.length();
    int[] badChar = new int[256];
    for (int i = 0; i < 256; i++) {
        badChar[i] = m;
    }
    for (int i = 0; i < m - 1; i++) {
        badChar[pattern.charAt(i)] = m - i - 1;
    }
    return badChar;
}

private int[] buildSuffix(String pattern) {
    int m = pattern.length();
    int[] suffix = new int[m];
    suffix[m - 1] = m;
    int f = 0, g = m - 1;
    for (int i = m - 2; i >= 0; i--) {
        if (i > g && suffix[i + m - 1 - f] < i - g) {
            suffix[i] = suffix[i + m - 1 - f];
        } else {
            if (i < g) {
                g = i;
            }
            f = i;
            while (g >= 0 && pattern.charAt(g) == pattern.charAt(g + m - 1 - f)) {
                g--;
            }
            suffix[i] = f - g;
        }
    }
    return suffix;
}

Boyer-Moore算法的时间复杂度是O(n + m)，其中n是主字符串的长度，m是模式字符串的长度。

这三种算法都是经典的字符串匹配算法，它们在实际应用中有不同的优劣势和适用范围。我们可以根据具体的应用场景选择适合的算法来实现字符串匹配。