一周一算法—— kmp算法

#技术 #算法

字符串匹配应该算是较为基础的算法,这里先从kmp算法开始,对于基础的暴力查找就不说了。

###介绍

其实大部分的字符串匹配算法与暴力查找的思想都大同小义,都是一步一步匹配查找串,在不匹配出现时,将串向后移动一定步数, 进行下一次的匹配。而移动的步数的不一致就形成了不一样的算法。如移动一步就是暴力搜索,而移动一步或者一步以上的算法又有几种, 它们的区别主要在于计算移动步数的方法的不一致上,具体的kmp算法, BM算法等。这儿具体先介绍KMP算法。

###算法描述

实际上对于KMP算法最为重要的就是匹配失败时的匹配串向后移动的步数。
这个步数的计算实际是基于部分匹配表的。实际上对于KMP算法的理解难度最大的地方也就在于通常说的next数组,而next数组,是可以根据 部分匹配表来确定的,而部分匹配相较于next数组更好理解,所以就先从部分匹配表开始。

####部分匹配表

首先我们假设这样一个匹配串abababca。先直接给出其部分匹配表如下示:

char:   | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

为了能够很好的说明部分匹配表的计算,给出一下的定义:

  • 前辍: 字条串中的所有以第一个字符开始,并且截止于最后一个字符之前的子字符串。如串snape的所有前缀串有s,sn,sna,snap
  • 后缀: 字符串中的所有以最后一个字符结尾,并且开始位置不为第一个字符的子字符串。 如串snape的所有后缀串有e,pe,ape,nape

有了以上的前缀,后缀的定义, 部分匹配表的单个值就可以用下面的一句话计算得到。

部分匹配表中的对应位置的值为其对应字串的最长的前缀与后缀相等时的长度

如串ababa 的前缀有a,ab,aba,abab, 后缀有a,ba,aba,baba。相等的前缀与后缀分别有a,aba。而aba长度为3大于a的长度为1, 因此在串ababa的对应value位置为3,同样对于串ababab, 可求得最长的匹配前后缀为abab,因此在部分匹配表中对应的位置值为4。

求得了部分匹配表,下一步就是在匹配过程中使用它,它如何使用呢?看下面的例子
假设匹配串为abababca, 搜索串为bacbababaabcbab,对于匹配串,其部分匹配如上面示。下面看匹配串与搜索串第一次匹配的位置,如下示:

bacbababaabcbab
=+
=abababca

从上面的匹配知,在匹配串的字符c时出现了不匹配,则此时需要将匹配串进行向后移动,以进行一下次匹配过程,在暴力搜索时,就是简单的向后移动一步即可进行下一次的 匹配,但在kmp算法中应该如何移动呢?先给出结论:

move_len = match_length - table[match_length - 1]

上面的match_length为当前已经匹配的字串的长度,如第一次匹配时仅匹配了字符a,则匹配长度为1,那么此时移动的距离为1-table[1-1],即1-table[0],table[0]值为0,则仅需要向 后移动一步,刚好与暴力搜索时一致,再看下一次匹配时。

bacbababaabcbab
===
==abababca

此时不存在匹配,匹配长度为0,按上面的公式不能计算出值,所以此时应该装简单的向后移动一步。公式此时修正为:

if (match_length > 0); then
    move_len = match_length - table[match_length - 1] 
else
    move_len = 1
fi

继续向下对比,如到达以下位置时:

bacbababaabcbab  
====+++++   
====abababca  

此时,在匹配串的字符b时出现了不匹配,当前的匹配长度为5,又table[5-1]为3,则按上面的公式,则move_len为2,即需要向后移动2,移动后的位置如下示:

bacbababaabcbab  
======+++   
====**abababca  

上面的*用于表示移动2位,可以看出,移动两个位置后,已经出现了3个位置的匹配,则仅需要继续向下一个字符进行比较即可。下一个字符a与b不相等,按上式计算需要向 后移动2位,得到移动后的位置如下示:

bacbababaabcbab  
========+   
======**abababca  

同样移动后,得到了一个已经匹配的位置。后面的步骤同上。

###移动规则的得来

根据上面的过程知道,按部分匹配表的移动过程是可以对暴力搜索时的匹配不成功时仅向后移动一步进行优化的,那么为什么按部分匹配向后移动是可行的呢?为什么 移动后在上一次搜索串的对比位置对比处的匹配的串的前面部分总是会与搜索串匹配呢?

其实可以从部分匹配值的得来中得到原因,部分匹配是如何得来的?部分匹配表中的值实际上是对应子串的最长的前缀与后缀匹配时的长度,这样相当于该串的后n个字符的值实际是与 串的前n的字符的相等的,而这n是能够得到的最大值,那么当出现不匹配时,因为上一个位置是匹配的,那么最后的n个字符是一定也是与搜索串匹配的,那么就说明前n个字符,也是与这部分 字条是相等的。则移动时将前n个字符与搜索串对应的这n个字条对应起来即可,那么就可以保证按搜索串的匹配,可以继续检查下一个字符的匹配情况。

###next数组的计算

好,从上面的部分匹配表已经是可以得到当不匹配出现时,一个部分优于暴力搜索的移动步数,那如何更加直接的在算法中利用部分匹配表呢?这就是next数组,同样我们先给出结果:

char:   | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
next:   | -1| 0 | 0 | 1 | 2 | 3 | 4 | 0 |

首先,不考虑这么多,从直观上来观察可以发现next数组实现上是value数组向后移动一位后,并且最左以-1填充的元素构成。那么具体是不是呢?对的就是,因为next数组实际就是由value数组经过以上 的变换得到,那为什么要进行这样的变换再生成一个next数组呢?因为在计算过程为了方便,更多的关注的是当前位置失配时,如何获取一个移动的位置,而value数组则是上一个匹配位置时最长相同前后缀的 值,将其向的移动一位, 则移动位数就由 已匹配的串的长度-上一个位置的最长相同前后缀的长度变成了失配的位置-失配时next数组的值,这样实际计算过程更加方便。其实next数组的存在个人觉得 更重要的是更方便计算。

next数组的计算过程利用了递归原则,如下:

假设对于值k,已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1,也即串p[0,j-1]的最长相同前后缀的长度为k,这样按next[j]
的规则(为 前面的串的value值),next[j] = k。下面从next[j]求next[j+1],分情况讨论:
(1)pk = pj, 那么就有p0 p1, ..., pk = pj-k pj-k+1, ..., pj,这样同理得到next[j+1] = k + 1 = next[j] + 1;
(2)pk ≠ pj, 那么就不能简单的由next[j]得到next[j+1]了,next[j+1]的计算过程就需要以其它方法了,不过由于存在n
    ext[j]=k,也即p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1,那么对于i,i>=0且i<k-1, 则必定会有
    pi pi+1, ..., pk-1 = pj-k+i, pj-k-i+1, ..., pj-1。这样对于p0 p1, ..., pk-1,我们假设next[k] = k-i, 则存在
    p0 p1, ..., pk-i-1 = pi pi+1, ..., pk-1, 则p0 p1, ..., pk-i-1 = pj-k+i, pj-k-i+1, ..., pj-1,则时如果
    pk-i = pj了,则如情况下,next[j+1] 就可以等于k-i+1,即next[j+1] = next[k] + 1, 若不存在,则可以继续递归下去。
    直到找到这样一个i,或者停止。

由上next数组的计算过程就可以实现为如下示:

    /**
     * 求next数组
     * @param char* p 匹配串
     * @param int   l 匹配串的长度
     * @param array n next数组
     * 
     * @return void
     */
    void getnext(char* p, int l, int n[])  
    {  
        int k = -1, j = 0;  
        n[0] = -1;  
        while (j < l - 1) {  
            //p[k]表示前缀,p[j]表示后缀  
            if (k == -1 || p[j] == p[k]) {  
                ++j, ++k;  
                n[j] = k;  
            } else {  
                k = n[k];  
            }  
        }  
    }

###匹配算法

经过前面的分析最后的匹配程序为:

    /**
     * 求next数组
     * @param char* s 搜索串
     * @param int   n 搜索串的长度
     * @param char* s 匹配串
     * @param int   n 匹配串的长度
     * @param array next next数组
     * 
     * @return int
     */
    int kmp(char* s, int n, char* p, int l, int next[])  
    {  
        int i = 0, j = 0;  
        int r = -1;
        while (i < n && j < l) {  
            //如果j = -1,或者当前字符匹配成功(即s[i] == p[j]),都令i++,j++      
            if (j == -1 || s[i] == p[j]) {  
                i++, j++;  
            } else {  
                //如果j != -1,且当前字符匹配失败(即s[i] != s[j]),则令 i 不变,j = next[j]      
                //next[j]即为j所对应的next值        
                j = next[j];  
            }  
        }  
        if (j == l) {
            r = i - j;
        }  
        return r;  
    }