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

字符串匹配是计算机中比较基础的算法之一，主要是用来判断一个字符串中是否包含和另一个字符串相同的子串。在工程实践中，字符串匹配算法具有广泛的应用，比如文本编辑器中的搜索和替换、数据库中的查询操作等等。本篇文章将通过Java语言详细探讨几种字符串匹配算法及其实现。

一、朴素字符串匹配算法

朴素字符串匹配算法是最简单和常见的字符串匹配算法，其实现思路是通过两个嵌套的循环遍历主串和模式串，将主串中所有可能的子串与模式串进行一一比较，找到第一个相同的子串则匹配成功。但这种算法的时间复杂度高达O(mn)，其中m和n分别为主串和模式串的长度，因此其适用范围比较有限。

下面是Java实现朴素字符串匹配算法的示范代码：

public static int naiveStringMatch(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;                              // 匹配失败
}

二、KMP字符串匹配算法

KMP字符串匹配算法（Knuuth-Morris-Pratt）是一种比朴素算法更优的字符串匹配算法，其核心思想是通过预处理模式串，使得在匹配过程中每次失配时可以尽可能地避免已经匹配过的字符。这种算法的时间复杂度为O(m+n)，其中m和n分别为主串和模式串的长度，因此具有很高的效率。

下面是Java实现KMP字符串匹配算法的示范代码：

public static int KMPStringMatch(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] next = getNext(pattern);          // 模式串的next数组
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        } else {
            j = next[j];                    // 失配时跳转到模式串的next位置
        }
    }
    if (j == m)
        return i - j;                       // 返回匹配位置下标
    else
        return -1;                          // 匹配失败
}

// 计算模式串的next数组
public static 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;
}

三、Boyer-Moore字符串匹配算法

Boyer-Moore字符串匹配算法是一种基于字符比较位置的字符串匹配算法，其核心思想是从模式串最后一个字符开始匹配，不匹配时通过预处理得到的坏字符表（bad character table）和好后缀表（good suffix table）来决定移动模式串的位置，尽可能地跳过已经匹配过的字符。这种算法的时间复杂度为O(mn)，但其在实际应用中常常比KMP算法更快，因为它可以跳过更多的无效匹配。

下面是Java实现Boyer-Moore字符串匹配算法的示范代码：

public static int BMStringMatch(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] bc = buildBC(pattern);            // 模式串的坏字符表
    int[] suffix = new int[m];              // 模式串的好后缀表
    boolean[] prefix = new boolean[m];      // 模式串的好后缀前缀表
    preprocess(pattern, suffix, prefix);    // 预处理模式串
    int i = 0;
    while (i <= n - m) {
        int j = m - 1;
        while (j >= 0 && text.charAt(i + j) == pattern.charAt(j)) {
            j--;
        }
        if (j < 0)                          // 匹配成功
            return i;
        else {
            int x = j - bc[text.charAt(i + j)];
            int y;
            if (j < m - 1) {
                y = moveBySuffix(j, suffix, prefix);
            } else {
                y = 1;
            }
            i += Math.max(x, y);
        }
    }
    return -1;                              // 匹配失败
}

// 计算模式串的坏字符表
public static int[] buildBC(String pattern) {
    int m = pattern.length();
    int[] bc = new int[256];
    Arrays.fill(bc, -1);
    for (int i = 0; i < m; i++) {
        bc[pattern.charAt(i)] = i;
    }
    return bc;
}

// 预处理模式串
public static void preprocess(String pattern, int[] suffix, boolean[] prefix) {
    int m = pattern.length();
    for (int i = 0; i < m; i++) {
        suffix[i] = -1;
        prefix[i] = false;
    }
    for (int i = 0; i < m - 1; i++) {
        int j = i;
        int k = 0;
        while (j >= 0 && pattern.charAt(j) == pattern.charAt(m - 1 - k)) {
            j--;
            k++;
            suffix[k] = j + 1;
        }
        if (j == -1)
            prefix[k] = true;
    }
}

// 根据好后缀表和好后缀前缀表计算移动距离
public static int moveBySuffix(int j, int[] suffix, boolean[] prefix) {
    int k = suffix[j + 1];
    if (k > -1)
        return j - k + 1;
    for (k = j + 2; k < suffix.length; k++) {
        if (prefix[suffix.length - k])
            return k;
    }
    return suffix.length;
}

综上所述，字符串匹配算法在实际应用中具有广泛的应用，Java作为一门广泛使用的编程语言，提供了丰富的字符串处理函数和类，方便开发者实现各种复杂的字符串匹配和操作功能，同时也为算法实现提供了良好的基础支持。在算法的选择和实现中，我们需要根据实际应用场景进行综合评估，选择最佳算法和优化手段来提高系统性能和用户体验。