KMP算法

  1. 云栖社区>
  2. 博客>
  3. 正文

KMP算法

colleen 2018-08-31 21:35:00 浏览395
展开阅读全文

问题描述

输入:一个文本串S,和一个模式串P
输出:若干行,每行包含一个整数,表示s2在s1中出现的位置

在一个母字符串S(文本串)中查找一个子字符串P(模式串)有很多方法。Knuth-Morris-Pratt 字符串查找算法(简称“KMP”)是一种最常见的改进算法,由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。

这个算法针对的是子串有对称属性,如果有对称属性,那么就需要向前查找是否有可以再次匹配的内容。

注意:这里的对称性,不是中心对称,而是中心字符块对称,比如不是abccba,而是abcabc这种对称。


KMP

一般最粗暴的方法,就是匹配失败后,一个字符一个字符往后挪来进行比较,比如:


img_dfa7f924bee9d5f0acf1512ec4a011f7.png
img_52937fa8505fb77fd444833271624efd.png

KMP可以在匹配过程中失配的情况下,有效地多往后面跳几个字符,加快匹配速度。
下面先直接给出KMP的算法流程:


img_b65010ffce96ed04d5cac369d7b46269.png
图一(a)
img_44940c0f9866edbdf5d139eb2376e1c2.png
图一(b)
img_f2e6f4bb054ab8b6b7e1c753f6162df2.png
图二(a)
img_9a0cc43cc168439c02bc8f8caceb121b.png
图二(b)

假设现在文本串S匹配到i位置,模式串P匹配到j位置

  • 当前字符匹配成功(即S[i] == P[j],图一),都令k++j++,继续匹配下一个字符;
  • 当前字符匹配失败(即S[i] != P[j],图二),则令 k不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j - next [j]位。

换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值(next 数组的求解会在下文详细阐述),即移动的实际位数为:j - next[j],且此值≥1。


next数组(前缀数组)

每一个模式串P都有有一个固定的next数组,它记录着字符串匹配过程中失配情况下可以向前多跳几个字符,当然它描述的也是子串的对称程度,程度越高,值越大,当然之前可能出现再匹配的机会就更大。

img_0e4e4047bda1e47fc68cf875ad28b91d.png

这个next数组的求法是KMP算法的关键,看到别的地方到处是数学公式推导,我这里用图示的方法方便大家理解。

img_fae95503c99290e391ecd70f8cda1adf.png
  • 红色:模式串P当前已经匹配好的相同前后缀
  • 蓝色:模式串P当前匹配的位置,就是j
  • 橙色:模式串P当前匹配的最长前缀的后一位,即为k

如果p[j] == p[k],则皆大欢喜, next[j] = next[j - 1] + 1
如果p[j] != p[k],只能寻找更短的相同前后缀匹配,我们看下图

img_bfbf4609ec3947ef5422e9b9cdab6ad3.png
  • 灰色:当前已经匹配好相同前后缀中的最长公共前后缀
  • 紫色:当前已经匹配好相同前后缀中的前缀的后一位

因为红色部分是已经匹配好的,所以既然第二个的后面为灰色部分,第一个的前面和后面也为灰色部分,接下来对应的,第二个前面的也为灰色部分。

查阅蓝色紫色是否匹配。

此时,又回到最初的那一步(递归),求解某个位置的next值是一个循环过程,不断检查 上一位的最长前缀的后一位.
如果相等next[j] = next[k] + 1,否则 k = next[k]


代码

//优化过后的next 数组求法
void GetNextval(char* p, int next[]) {
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1){
        //p[k]表示前缀,p[j]表示后缀  
        if (k == -1 || p[j] == p[k]){
            ++j;
            ++k;
            //较之前next数组求法,改动在下面4行
            if (p[j] != p[k])
                next[j] = k;   //之前只有这一行
            else
                //因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
                next[j] = next[k];
        }
        else{
            k = next[k];
        }
    }
}

参考链接

网友评论

登录后评论
0/500
评论
colleen
+ 关注