最快的字符串匹配算法及其复杂度

匹配算法中，最快的算法是KMP算法，它的时间复杂度为O(n+m)，其中n为主串长度，m为模式串长度。KMP算法的核心思想是利用已经匹配过的信息，尽量减少模式串与主串的匹配次数。具体实现方法是通过预处理模式串，得到一个next数组，用于指导匹配过程中的跳转。KMP算法的代码如下：

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

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