Java 字符串匹配算法示例

为了匹配字符串，可以使用经典的 KMP（Knuth-Morris-Pratt）算法。其基本思想是，在匹配过程中，如果出现不匹配的情况，我们应该避免回溯已经匹配的部分，而是利用已经匹配的信息快速地跳过一些无法匹配的字符。

以下是一个 Java 实现的示例代码：

public class KMPSubstringSearch {
    public static int search(String text, String pattern) {
        int N = text.length();
        int M = pattern.length();

        // 构造最长公共前后缀 lps 数组
        int[] lps = new int[M];
        int i = 1;
        int len = 0;
        while (i < M) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                lps[i++] = ++len;
            } else {
                if (len == 0) {
                    lps[i++] = 0;
                } else {
                    len = lps[len - 1];
                }
            }
        }

        // 在文本中查找匹配
        int j = 0;
        i = 0;
        while (i < N) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            }
            if (j == M) {
                return i - M;
            } else if (i < N && text.charAt(i) != pattern.charAt(j)) {
                if (j == 0) {
                    i++;
                } else {
                    j = lps[j - 1];
                }
            }
        }
        return -1;
    }
}

在这个示例代码中，我们首先构造了一个最长公共前后缀 lps 数组，然后使用这个数组进行匹配。具体来说，我们维护两个索引 i 和 j，分别指向文本和模式字符串的当前位置，然后不断比较这两个位置上的字符。如果匹配成功，两个索引都向前移动一位；如果不匹配，我们应该尽量不回溯已经匹配的部分，而是通过 lps 数组快速地跳过一些字符。如果最终 j 能够到达模式字符串的末尾，说明匹配成功。否则，返回 -1 表示没有找到匹配的子串。