KMP算法——字符串子串匹配

发表于 更新于 分类于 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

KMP算法解决了子串在字符串中定位的问题，即子串查找与匹配。KMP算法是三位大佬D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。

模板题 洛谷P3375

暴力做法

从左到右一个个匹配，如果某个字符不匹配，就将子串右移一位重新匹配。

复杂度\(\mathcal{O}(nm)\)，其中n为主串长度，m为子串长度

优化思路

匹配失败后应该可以尽可能多地向右移动，以减少无效的匹配。因此需要确定匹配失败后向右移动不影响匹配结果的尽可能多的位数是多少。

KMP的重点就是当某一个字符与主串不匹配时，我们应该知道指向子串位置的j指针要移动到哪

规律推导

具体例子

  • 例1

    1
    2
    ABACBDCHIJK (i)
    ABAD  (j)
    • 当D不匹配时，子串应该向后移两位，因为A相同可以匹配

  • 例2

    1
    2
    ABCABCDHIJK  (i)
    ABCABB  (j)
    • 当C与D不匹配时，子串向后移3位，因为AB相同可以匹配

我们可以总结出，子串移动位置的特点就是，尽量确保前k位都是匹配的，那么j会到k+1

即子串需要确保\(P[0,k-1]==P[j-k, j-1]\)

在例2中，\(k=2, j=5\)。移动后\(j=k=2\)

求出k

由于子串P的每一个位置都可能发生不匹配的情况，因此需要计算每一个位置的j对应的k，用一个数组next来保存，\({next}[j] = k\) 表示，j的下一个位置k

递推法

对一位j而言，我们需要判断该位置的前几位是否与子串开头的几位相同。

假设我们已经算出前\(j-1\)位的next，那么只需要考虑next[j-1]

若next[j-1] == k ，那么当P[k]==P[j-1]时，next[j] = k+1，否则k=next[k]，直到P[k] == P[j-1]或k == -1

后一种情况是典型的动态规划思想，一开始可能不太容易想明白，下面再举一个例子。

next[j]=next[k]示意图

对于\(P[j-k,j-1]\) ，我们需要找到j前面尽可能多的与模式串开头相同的串，由于该串的长度只可能小于k，那么这个串一定与k前面的串相同，即next[j]的结果取决于next[k]，那么需要不断迭代k=next[k]。

直到P[j-1] == P[k]，这个时候可以直接用next[k]的结果，否则k一定会不断迭代直到-1，这时next[j] = k+1，可以与P[k]==P[j-1]的情况合并。

这时next[k]相当于长度为k-1的前缀字符串内部，长度最长的相等的前缀与后缀。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
int* getNext(string p) {
    int* next = new int[p.length()];
    next[0] = -1;
    int j = 0;
    int k = -1;
    while(j < p.length() - 1){
    	if(k == -1 || p[j] == p[k])
    		next[++j] = ++k;
    	else
    		k = next[k];
	}
    return next;
}

  • 当j为0时不匹配

    j不可能继续向前，若next[0]设为0就会陷入死循环，所以next[0]设为-1标记不可能继续向前这一性质

  • 如果P[k]!=P[j]

    k=next[k]原理图

字符串匹配完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int *next = getNext(s2);
int i = 0, j = 0;
while(i < s1.length()){
    if(j == -1 || s1[i] == s2[j]){
        if(j+1 == s2.length()){
            cout << i - j + 1 << endl;
            j = next[j];
        }else{
            i++; 
            j++;
        }
    }
    else{
        j = next[j];
    }
}

证明时间复杂度为\(\mathcal{O}(n)\)

借用势能的概念，构造表达式，使表达式在while循环中单调递增，然后已知初始值和结束值

定义势能函数\(k = 2i-j\)，考察算法过程的k变化 - 初始时，\(k = 0\) - 论断：每经过一次循环, k至少增加1 - 若if判断为true，则i、j同时加1，故k至少加1 - 否则，i不变，j至少减1，故k至少加1 - 算法结束时，\(k = 2i-j \leq 2(n-1)-(-1) = 2n-1\)

额外的辅助空间复杂度为\(\mathcal{O}(n)\)

进一步改进next

上述内容足以完成开篇所列的洛谷模板题，但就效率而言还不够好，下面一种情况就是不必要的。

1
2
ABACBC
ABAB

若匹配到第3位C与B，按照之前的做法应该回溯到next[3]==1中，但由于P[next[3]]==P[3]，这样的回溯没有意义，应该进一步回溯到不相等的情况。

若排在前面的字符的回溯就采用这种思想，那么可以确保后面的字符只需经过一次回溯就可以达到不相等这种最优的情况。

getNext代码修改如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int* getNext(string p) {
    int* next = new int[p.length()];
    next[0] = -1;
    int j = 0;
    int k = -1;
    while(j < p.length() - 1){
    	if(k == -1 || p[j] == p[k]){
            if(p[++j] == p[++k]){
                next[j] = next[k];
            }else{
                next[j] = k;
            }
        }
    	else
    		k = next[k];
	}
    return next;
}

参考文献

[1] https://www.cnblogs.com/yjiyjige/p/3263858.html 详解KMP算法