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

字符串匹配算法，是在一个字符串中查找另一个字符串出现位置的基本操作，广泛应用于编程领域。常见的字符串匹配算法有暴力匹配算法、KMP算法、Boyer-Moore算法等，这里主要介绍Java函数实现字符串匹配的算法。

1. 暴力匹配算法

暴力匹配算法又称为朴素匹配算法，从主串的 个字符开始和子串进行匹配，如果匹配成功，则在主串中查找下一个字符，直到找到所有匹配项。如果匹配失败，则移动子串的位置，继续匹配。

Java代码实现如下：

public static int violentMatch(String str, String pattern) {
    int sLen = str.length();
    int pLen = pattern.length();
    int i = 0, j = 0;
    while (i < sLen && j < pLen) {
        if (str.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j == pLen) {
        return i - j;
    } else {
        return -1;
    }
}

2. KMP算法

KMP算法是一种改进的字符串匹配算法，通过把模式串的前后缀相同的部分预先计算出来，减少了不必要的匹配次数。具体步骤如下：

1）计算模式串的next数组。next[j]表示模式串的长度为j时，最长相同前缀和后缀的长度。

2）利用next数组进行匹配。从主串和模式串的头部开始匹配，当发现匹配失败时，将模式串后移i-next[i]位，i为已匹配的模式串中的最后一个字符的下标。

Java代码实现如下：

public static int kmpMatch(String str, String pattern) {
    int sLen = str.length();
    int pLen = pattern.length();
    int[] next = getNext(pattern);
    int i = 0, j = 0;
    while (i < sLen && j < pLen) {
        if (j == -1 || str.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. Boyer-Moore算法

Boyer-Moore算法是一种高效的字符串匹配算法，通过对于子串中最右边的字符进行比较，快速地排除不匹配的情况。具体步骤如下：

1）将模式串从右向左进行匹配，在模式串中从右到左有一段前缀，使得这段前缀中的每个字符都不等于末尾字符，找到这个前缀，移动模式串的位置。

2）在主串中利用模式串最右端的字符进行比较，若匹配，则继续匹配，否则移动模式串的位置。

Java代码实现如下：

public static int boyerMooreMatch(String str, String pattern) {
    int sLen = str.length();
    int pLen = pattern.length();
    int[] badChar = new int[256];
    int[] suffix = new int[pLen];
    boolean[] prefix = new boolean[pLen];
    generateBadChar(pattern, badChar);
    generateGoodSuffix(pattern, suffix, prefix);
    int i = 0, j = 0;
    while (i < sLen - pLen + j + 1) {
        while (j < pLen && str.charAt(i + j) == pattern.charAt(j)) {
            j++;
        }
        if (j == pLen) {
            return i;
        }
        int k = badChar[str.charAt(i + j)];
        int m = j - suffix[j];
        if (k > m) {
            i = i + k;
        } else {
            if (j == pLen - 1) {
                i++;
            } else {
                i = i + m;
            }
        }
        j = 0;
    }
    return -1;
}

public static void generateBadChar(String pattern, int[] badChar) {
    int pLen = pattern.length();
    for (int i = 0; i < 256; i++) {
        badChar[i] = pLen;
    }
    for (int i = 0; i < pLen - 1; i++) {
        badChar[pattern.charAt(i)] = pLen - 1 - i;
    }
}

public static void generateGoodSuffix(String pattern, int[] suffix, boolean[] prefix) {
    int pLen = pattern.length();
    for (int i = 0; i < pLen; i++) {
        suffix[i] = pLen;
        prefix[i] = false;
    }
    for (int i = 0; i < pLen - 1; i++) {
        int j = i;
        int k = 0;
        while (j >= 0 && pattern.charAt(j) == pattern.charAt(pLen - 1 - k)) {
            j--;
            k++;
            suffix[k] = j + 1;
        }
        if (j == -1) {
            prefix[k] = true;
        }
    }
}

总结：

以上是三种常见的Java函数实现字符串匹配的算法，包括暴力匹配算法、KMP算法和Boyer-Moore算法。不同的算法适用于不同的场景，选择合适的算法可以提高算法的效率，从而提高程序的性能。