模式匹配KMP算法

注：文中均为伪代码。主要是展示算法思想和实现方式

算法要求

给定主串 S 和子串 T，要求返回 T 在 S 中第一次出现的位置，若不存在，返回 -1；

暴力匹配

以 S 的第 1 个字符为起点，逐个与 T 中字符比较，若匹配失败，起点向前进一位，即第二次匹配从第 2 个字符开始。直至匹配成功或无法匹配。

代码示例：

int Index(String s, String t, int pos) {
    int k = 0, j = 0;
    while (k < s.length && j < t.length) {
        if (s[k] == t[j]) {
            k++;
            j++;
        }
        else {
            k = k - j + 1;	//k-j为当前起点位置，+1为下次匹配起点
            j = 0;
        }
    }
    if (j >= t.length)
        return (k - t.length);
    return -1;
}

时间复杂度：O(mn)

KMP算法

算法框架

暴力匹配的缺点在于每次匹配失败主串和子串指针都要回到起点。KMP算法对此进行了优化，匹配失败后，主串指针不动，子串指针也不用回到起点，而是回溯到适当位置。

如上图所示，假设现在在位置 x 处匹配失败了，如果子串 t 中在 x 前面存在与起点相同的一段字符串，分别记作 D 与 C ，又因为 AC，BD 已经匹配，所以这四个串完全相同，那么，就可以将子串向右滑动，即子串指针向前回溯一个到 C 的末尾，让 C 与 B 对齐，这样 BC 就匹配好了，所以主串指针不用回溯，继续向后比较即可。可以看出，如果存在这样的情况，则 C 的长度越长，匹配速度越快。所以在算法中，我们需要求出满足条件的最长的串 C。

看起来速度会提升不少，但是问题来了，它一步跳过那么多字符，有没有可能会漏掉中间可以成功匹配的情况呢？答案是不会。可以反证法，假如中间部分可以匹配成功，即 t 不用向右滑那么多就可以匹配成功，那么就存在更长的 C’（C向右加长）与 B’（B向左加长）相匹配，那么就有对应的 D’ （D向左加长）。这与 C 和 D 是 t 中符合条件的最长串相矛盾。

正确性没有问题了，如何实现呢？可以看出，子串 t 的回溯位置是由其本身的组成决定的，在不同位置匹配失败需要回溯的位置不同，在 t[j] 匹配失败需要回溯到的位置可以记为 next[j]。我们先不考虑 next 数组如何求，先写出算法框架。

代码示例如下：

#define Max_Strlen 1024
int next[Max_Strlen];	//已经算好
int KMP_index(String s, String t) {
    int i = 0, j = 0;
    while (i < s.length && j < t.length) {
        if (j == -1 || s[i] == t[j]) {
            i++;
            j++;
        }
        else j = next[j];
    }
    if (j >= t.length)
        return (i - t.length);
    return -1;
}

第六行 j == -1 是因为记 next[0] = -1

时间复杂度：O(m+n)

计算next[j]

暴力穷举法

int next1(String t, int j) {
    String str1, str2;
    int k = j;
    do {
        k--;
        str1 = subString(t, 0, k);	//对t，从t[0]开始，截取长度为 k 的串
        str2 = subString(t, j-k, k);
    }
    while (k && strncmp(str1, str2, k));
    //strncmp比较str1与str2前k个元素是否完全相同
    if (k == 0)
        return 0;
    return k;
}

改进穷举法

先判断尾元素是否相等，再比较串是否相等

int next2(String t, int j) {
    for (int k = j - 2; k >= 0; k--) {
        if (t[k] == t[j-1])
            if (strncmp(t, &t[j-k-1], k+1) == 0)
                return (k + 1);
    }
    return 0;
}

递推法

void get_next(char t[], int next[]) {
    int j = 0, k = -1;
    next[0] = -1;
    while(j < 12) {
        if (k == -1 || t[j] == t[k])
            next[++j] = ++k;
        else
            k = next[k];
    }
}

显然，递推法的效率最高，但是，递推法还有可以优化的地方，比如模式串为aaaab，主串为aaabaaaab，则当第一次匹配失败时，i = 3，j = 3，根据next[j]的指示，下一次比较 j = 2，然后比较 j = 1, j = 0。但实际上，因为模式串前四个都是相同的，所以下次匹配一定失败。所以可以做如下优化：当 s[i] != s[j] 时，若 t[j] == t[next[j]]，则直接跳过一次匹配，匹配 t[j] 与 t[next[next[j]]]。

代码示例：

void next_val(char t[], int next[]) {
    int j = 0, k = -1;
    next[0] = -1;
    while(j < t.length) {
        if (k == -1 || t[j] == t[k]) {
            ++j; ++k;
            if (t[j] != t[k])
                next[j] = k;
            else
                next[j] = next[k];
        }
        else
            k = next[k];
    }
}

完整代码

可直接运行。

void Set_Next(vector<int> &next, string t) {
    int j = 0, k = -1;
    next[0] = -1;
    while(j < t.length()) {
        if (k == -1 || t[j] == t[k]) {
            ++j; 
            ++k;
            if (t[j] != t[k]) next[j] = k;
            else next[j] = next[k];
        }
        else k = next[k];
    }
}
int strStr(string s, string t) {
    int m = s.length(), n = t.length();
    vector<int> next(n+1);	
    Set_Next(next, t);
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (j == -1 || s[i] == t[j]) {
            ++i;
            ++j;
        }
        else j = next[j];
    }
    if (j >= n) return (i - t.length());
    return -1;
}

cpp 比 c 优雅多了😘