Java函数：字符串匹配

字符串匹配是计算机科学中的一个基础操作。通俗来说，它是指在一个文本串中查找一个模式串的过程。在Java中，有多种方式可以实现字符串匹配操作，包括暴力匹配、KMP算法、Boyer-Moore算法等等。在本文中，我们将介绍其中几种常用的实现方式。

1. 暴力匹配

暴力匹配是最简单直接的一种算法实现方式。其思想是将模式串从头到尾依次与文本串中的子串进行比较，直到找到匹配的位置或者遍历完整个文本串。如果模式串的长度为m，文本串的长度为n，则暴力匹配的时间复杂度为O(nm)。

下面是一个基于暴力匹配算法实现的Java函数：

public static int bruteForce(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; // 匹配失败，返回-1
}

其中，text表示文本串，pattern表示模式串。这个函数会依次遍历文本串中的每一个子串，与模式串进行比较。如果匹配成功，则返回模式串在文本串中的起始位置；否则，返回-1。

2. KMP算法

KMP算法是一种比暴力匹配更高效的字符串匹配算法。其核心思想是利用已匹配的信息避免了在不必要的位置上重复匹配，从而缩短了匹配时间。具体来说，它通过预先处理出模式串的最长公共前后缀，以及模式串在此前后缀上的匹配信息，在匹配过程中利用这些信息跳过一些不必要的位置。

下面是一个基于KMP算法实现的Java函数：

public static int kmp(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] next = getNext(pattern);
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        if (j == m) {
            return i - m + 1; // 匹配成功，返回模式串在文本串中的起始位置
        }
    }
    return -1; // 匹配失败，返回-1
}

private static int[] getNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

其中，kmp函数即为KMP算法的实现，getNext函数用于计算模式串的最长公共前后缀数组。这个函数在匹配过程中利用next数组跳过一些不必要的位置，从而提高了算法的效率。

3. Boyer-Moore算法

Boyer-Moore算法是一种比KMP算法更高效的字符串匹配算法。其核心思想是尽可能地利用模式串中的信息，在匹配过程中快速跳过不需要比较的字符。具体来说，它分别从模式串的末尾和文本串中靠近末尾的位置开始比较，如果发现有不匹配的字符，则根据预先计算好的移动距离表快速移动模式串，直到重新对齐为止。

下面是一个基于Boyer-Moore算法实现的Java函数：

public static int boyerMoore(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] badChar = getBadChar(pattern);
    int[] goodSuffix = getGoodSuffix(pattern);
    int j = m - 1;
    int i = j;
    while (j >= 0 && i < n) {
        if (text.charAt(i) == pattern.charAt(j)) {
            i--;
            j--;
        } else {
            i = i + m - Math.min(j, 1 + badChar[text.charAt(i)]); // 利用坏字符和好后缀规则移动模式串
            j = m - 1;
        }
    }
    if (j < 0) {
        return i + 1; // 匹配成功，返回模式串在文本串中的起始位置
    } else {
        return -1; // 匹配失败，返回-1
    }
}

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

private static int[] getGoodSuffix(String pattern) {
    int m = pattern.length();
    int[] goodSuffix = new int[m];
    int[] suffix = getSuffix(pattern);
    for (int i = 0; i < m; i++) {
        goodSuffix[i] = m;
    }
    for (int i = m - 2; i >= 0; i--) {
        if (suffix[i] == i + 1) { // 如果长度为i+1的后缀是模式串的前缀
            for (int j = 0; j < m - i - 1; j++) {
                if (goodSuffix[j] == m) { // 如果这个位置还未被更新
                    goodSuffix[j] = m - i - 1;
                }
            }
        }
    }
    for (int i = 0; i < m - 1; i++) {
        goodSuffix[m - 1 - suffix[i]] = m - i - 1;
    }
    return goodSuffix;
}

private static int[] getSuffix(String pattern) {
    int m = pattern.length();
    int[] suffix = new int[m];
    suffix[m - 1] = m;
    int j = m - 1;
    for (int i = m - 2; i >= 0; i--) {
        while (j < m - 1 && pattern.charAt(i) != pattern.charAt(j)) {
            j = suffix[j + 1] - 1;
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j--;
        }
        suffix[i] = j + 1;
    }
    return suffix;
}

其中，boyerMoore函数即为Boyer-Moore算法的实现，getBadChar和getGoodSuffix函数分别用于计算坏字符表和好后缀表，用于快速移动模式串。

4. 总结

本文介绍了几种常用的字符串匹配算法的Java实现方式，包括暴力匹配、KMP算法和Boyer-Moore算法。这些算法各有优缺点，可以根据具体场景选择合适的算法实现。在实践中，我们应该尽量从算法本身的角度考虑问题，对算法进行优化，从而提高其效率。