多模字符串匹配算法原理及Java实现代码

多模字符串匹配算法原理及Java实现代码攻略

多模字符串匹配算法是在一个文本串中同时匹配多个模式串的算法。常见的多模匹配算法有Trie树、AC自动机等，本文介绍的是KMP算法。

KMP算法原理

KMP算法的核心思想是利用已知信息，避免不必要的匹配。即：对于模式串中的每一个位置，找到该位置之前的子串的最长公共前后缀，并记录在next[]数组中。当匹配过程中发生不匹配，利用next[]数组中的信息，跳过一定的无需匹配的子串，再进行匹配。这样能有效减少匹配次数，提高匹配速度。

具体实现过程如下：

1. 预处理模式串，生成next[]数组。
2. 从模式串的第2个字符(即P[1])开始匹配，记录下匹配过程中每个字符之前的最长公共前后缀长度。
3. 如果发现某个字符与前面的字符不匹配，则利用记录的信息进行跳过。
4. 在文本串中匹配模式串。
5. 从文本串的第1个字符开始匹配，利用next[]数组跳过不必要的匹配，加快匹配速度。

KMP算法Java实现代码

public class KMP {
    public int[] getNext(String t) {
        int[] next = new int[t.length()];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < t.length() - 1) {
            if (j == -1 || t.charAt(i) == t.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    public int kmpSearch(String s, String t) {
        int[] next = getNext(t);
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (j == -1 || s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == t.length()) {
            return i - j;
        } else {
            return -1;
        }
    }
}

示例说明

假设我们要在文本串“abababca”中查找模式串“abc”：

1. 预处理模式串（代码详见上文），得到next[]数组：[-1, 0, 0, 0]
2. 从文本串的第1个字符“a”开始，与模式串的第1个字符“a”匹配，接着匹配第2个字符“b”，仍然匹配，匹配至第6个字符时与模式串不匹配，利用next[]数组跳过2个字符，继续与模式串匹配，在第7个字符处匹配成功，返回结果6。
3. 完整代码如下：

public class Main {
    public static void main(String[] args) {
        String s = "abababca";
        String t = "abc";
        KMP kmp = new KMP();
        int index = kmp.kmpSearch(s, t);
        if (index != -1) {
            System.out.println("匹配成功，位置为：" + index);
        } else {
            System.out.println("未找到该模式串");
        }
    }
}

输出结果为：“匹配成功，位置为：6”。