KMP

Posted on | In |
Words count in article: | Reading time ≈
字符串匹配是个十分经典而又十分有意义的一个问题, 在搜索信息时被广泛使用, 例如浏览器筛选信息, 编辑文本时的全局查找, DNA序列搜索等等. 对于应用如此广泛的问题当然要有十分快速的解决方法才好, 这里介绍的是复杂度最低的算法(应该没有比这个更好了吧.). 即KMP算法(Knuth-Morris-Pratt算法, 由此三人发明). 其时间复杂度为线性复杂度即O(n+m).(n和m分别为文本长度和匹配模式长度).

思想

与最简单的字符串匹配算法(每次比较完成后平移一个位置)相比, KMP主要利用了匹配过程中模式串本身的信息, 使得每次平移不是一个而是与之前匹配结果有关的一个值. 为了实现上述目的, 我们要对模式串进行分析处理, 生成一个前缀函数, 用以记录模式串内心信息与联系. 下图可以形象解释这一问题:

例

对于上图中, 当匹配到模式中第六个元素与文本中不对应时, 简单方法是平移1后继续从第一个开始匹配, 而KMP借助于前主函数, 知道平移一个接着匹配是一定不会匹配成功的, 因此可以直接平移两个并且再接着匹配时也不用从第一个开始匹配, 直接从第四个进行匹配即可.

前缀函数

模式的前缀函数包含模式与其子身的偏移进行匹配的信息. 简单来说, 前缀函数就是一个数组, 用来对应模式对于位置可以与模式本身前缀匹配长度. 例如: p为模式串, a[7] = 2, a是前缀函数, a[7]表示对应于模式的第8个元素, 前匹配函数为2表示, p[7] == p[2], 并且p[0-2]与p[5-7]是一致的. 一般的, 对于a[i] = n表示, p[0-n]=p[(i-n) - i], 即在第i个节点(对于模式串来说)匹配失败时将模式串索引为a[i-1]对应的元素与当前匹配到的文本前一个位置对齐即可以继续接着匹配. 以上图为例, a[4]=2; 在匹配第5个元素是(c)时出错, 此时只需要将模式串索引为a[4] = 2与文本中当前匹配到的元素(a)前一个(a)对齐, 然后接着从原来匹配出错的位置继续匹配即可.

前缀函数

前缀函数的获取其实本身就是一个字符串匹配问题, 是自己的后面的部分与前面进行匹配. 也就是对于任意的一个索引i, 我们要找到最大的n使得p[0-n] =p[(i-n) - i], 这其实与文本与模式串匹配是一样的, 不过文本与模式串匹配时是要找到满足p[0-n] = T[(i-n) - i](此处n与前面不一样, 前面n是一个变量,这里n指代模式串长度)的所有的i. 需要注意一点, 空字符串与所有字符串都可以匹配. 此时的操作有点类似与DP, 但又不一样. 其思想为: 始终存在一个数值k用于记录当前匹配到的最长前缀, 即满足p[0-n] = p[(i-n)-i]的最大的n. 随后考察索引i+1位置的情况. 此时, 如果p[k+1] = p[i+1], 则k应该增加1, 并且索引i+1的前缀函数为增加后的k值. 因为此时满足p[0-(k+1)] = p[(i-k)-(i+1)]; 当p[k+1] != p[i+1]时, 我们应该注意到, p[k] = p[a[k]], 这是由于当考察到第i+1时, 其前i个的前缀函数已经获得了. 此时对于前i个元素, 即有p[0-n] = p[(m-n)-m],(m=0,1,…i). n即为a[m].所以p[a[m]] = p[m]. 而在这里k = a[i](由前面所述k的定义可知). 所以, 我们可以令k = a[k]来获得索引i所对应的前缀串的最后一个元素的前缀函数.此时利用前缀的传递性, 即p[i] = p[a[i]] = p[a[a[i]]] = … 可以得到, 此时新获得的k依然满足k的定义, 即满足p[0-k] = p[(i-k), i]. 于是我们可以以该k值继续进行判断p[k+1] = p[i+1]?, 对应于出现的不同情况处理与先前所述一致. 令k = a[k]可以看成一个回溯, 其终止条件为要么查找到头依然没有找到满足条件的p[k+1] = p[i+1], 此时应该将模式串前一个位置(假想的空字符)平移到第i的位置, 即对应的a[i+1] = -1, 或者出现p[k+1] = p[i+1]. 这里前面突然出现的-1可能有写不好理解, 其实就是我们假想模式串前面有一个空字符, 这是为了方便我们处理而进行的一个假想的构造, 其索引就应该是-1, 空字符串与所以字符均匹配. 当a[i] = -1时表示, 将模式串空字符与当前i对齐, 即将模式串第一个元素与i+1对齐.

匹配

就像之前所述, 前缀函数相当与一个字符串匹配, 此时进行匹配的操作与计算前缀函数基本一致, 不过前缀函数匹配的是同一字符串进行匹配, 文本与模式串的匹配则是两个不同串进行匹配, 且此时前缀函数已经获得可以直接使用. 整体操作与前缀串差不多, 就增加了一个判断是否查找到完整子串这一步. 具体看代码即可.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 获取前缀函数
int* COMPUTE_PREFIX_FUNCTION(char a[])
{
    int num = strlen(a);
    int *w = new int[num];
    w[0] = -1;
    int k = -1;
    for(int i=1;i<num; i++)
    {
        while(k >= 0 && a[k+1] != a[i])
            k = a[k];
        if(a[k+1] == a[i])
            k++;
        w[i] = k;
    }
    return w;
}

// 匹配
void KMP_MATCHER(char T[], char p[])
{
    int T_NUM = strlen(T);
    int p_NUM = strlen(p);
    int *PREFIX_FUNCTION = COMPUTE_PREFIX_FUNCTION(p);
    int k=-1;
    for(int i=0;i<T_NUM; i++)
    {
        while(k >= 0 && p[k+1] != T[i])
        {
            k = PREFIX_FUNCTION[k];
        }
        if(p[k+1] == T[i])
            k++;
        if(k == p_NUM-1)
        {
            cout<<i-p_NUM+2<<" pattern occurs!!!"<<endl;
            k = PREFIX_FUNCTION[k];
        }
    }
}