Java函数实现字符串模式匹配算法

字符串模式匹配算法是指在一串字符串中寻找特定的模式子串的算法。常用的字符串模式匹配算法有暴力匹配算法、KMP算法和Boyer-Moore算法等。

1. 暴力匹配算法（Brute Force Algorithm）是最简单直观的字符串模式匹配算法。它的基本思想是从主串的 个字符开始，逐个字符地和模式串进行比较。如果匹配，则继续比较下一个字符，直到模式串的最后一个字符。如果匹配成功，则返回匹配的位置；如果匹配失败，则主串和模式串都向后移动一位，继续比较下一个字符。直到找到匹配或者主串被匹配完。

public static int bruteForce(String source, String pattern) {
    int sourceLen = source.length();
    int patternLen = pattern.length();
    for (int i = 0; i <= sourceLen - patternLen; i++) {
        int j;
        for (j = 0; j < patternLen; j++) {
            if (source.charAt(i + j) != pattern.charAt(j))
                break;
        }
        if (j == patternLen)
            return i;
    }
    return -1;
}

2. KMP算法（Knuth-Morris-Pratt Algorithm）是一种高效的字符串匹配算法。它的核心思想是：当遇到不匹配的字符时，根据已经匹配过的部分，能够跳过一些不匹配的字符，减少比较次数。具体实现中，KMP算法通过计算模式串的前缀和后缀的最大长度信息，构建一个部分匹配表，根据该表进行匹配。

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

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

3. Boyer-Moore算法是一种高效的字符串匹配算法。它的核心思想是：从模式串的尾部开始匹配，如果不匹配，则根据坏字符规则和好后缀规则调整主串和模式串的位置，使得匹配更快。具体实现中，Boyer-Moore算法通过预处理模式串，计算坏字符表和好后缀表，根据这些表进行匹配。

public static int boyerMoore(String source, String pattern) {
    int sourceLen = source.length();
    int patternLen = pattern.length();
    int[] badChar = new int[256];
    int[] suffix = new int[patternLen];
    for (int i = 0; i < 256; i++) {
        badChar[i] = -1;
    }
    generateBadChar(pattern, badChar);
    generateSuffix(pattern, suffix);
    int i = 0;
    while (i <= sourceLen - patternLen) {
        int j = patternLen - 1;
        while (j >= 0 && source.charAt(i + j) == pattern.charAt(j)) {
            j--;
        }
        if (j < 0) {
            return i;
        } else {
            i += Math.max(suffix[j], j - badChar[(int)source.charAt(i + j)]);
        }
    }
    return -1;
}

private static void generateBadChar(String pattern, int[] badChar) {
    int patternLen = pattern.length();
    for (int i = 0; i < patternLen; i++) {
        badChar[(int)pattern.charAt(i)] = i;
    }
}

private static void generateSuffix(String pattern, int[] suffix) {
    int patternLen = pattern.length();
    int[] next = new int[patternLen];
    next[patternLen - 1] = patternLen;
    int j;
    for (int i = patternLen - 2; i >= 0; i--) {
        j = i;
        while (j >= 0 && pattern.charAt(j) == pattern.charAt(patternLen - 1 - i + j)) {
            j--;
        }
        next[i] = i - j;
    }
    for (int i = 0; i < patternLen - 1; i++) {
        suffix[i] = next[patternLen - 1 - i];
    }
}

以上是Java实现的三种字符串模式匹配算法。这些算法有不同的优势和适用场景，对于不同类型的字符串匹配问题，可以选择最适合的算法来解决。