Pattern-Matching-1.KMP算法

许久之前的数据结构课上就已经学过大名鼎鼎的KMP算法，可是学一次忘一次，最近又要使用这个令人头疼的算法，于是打算把他记下来。

 

思考这样一个问题，给定了两个字符串：X=“bacbababababcaa”，Y="ababababca"。如何来判定Y是否是X的字串？

 

传统的朴素匹配方法，肯定是做一次双重循环，让Y中的每个字符与X中的每个字符一一匹配，如果刚好可以匹配上，那么Y就是X的字串了。可是这种方法有着很多的不必要的比较。于是，KMP算法的思想便是跳过这些不必要的操作。

 

KMP的关键问题是当循环中两个串当前的字符不匹配时，下一步应该比较那个字符？这个问题事实上也是算法改进的关键问题。

 

由当前不匹配字符到下一个被比较字符，我们可以看作一次“跳跃”，于是我们的问题便变成了-”跳跃“的规则是什么？

 

为了实现这种”跳跃“，我们引入了一个next数组，他的长度为匹配串pattern的长度，数组上的每个元素代表了匹配串当前字符不匹配时应该”跳跃“后进行下一次匹配的索引。

 

有了这些理论基础我们便可以写出KMP算法。

 

伪码参考算法导论，下面贴出详细代码。

/**
 * KMP算法，返回第一个字串的起始位置，如果pattern非s字串返回-1 
 * 
 */
int kmpMatcher(char* s, char* pattern)
{
    int m = strlen(pattern);
    int n = strlen(s);
    int* next = new int[m];
    computeNext(pattern,next,m);
    int q=-1;
    for(int i=0; i<n ; ++i){
        while(q>=0 && pattern[q+1]!=s[i]){
            // 不匹配情况 
            q=next[q];
        }
        if(pattern[q+1]==s[i]){
            // 匹配情况下，继续 
            q=q+1;
        }
        if(q==m-1){
            return i-m+1;
        }
    }
    return -1;  // doesn't match
}

 

接下来就是算法中的next数组获取问题。

 

假设当前我们要获取pattern串中i号位置的next值，即next[i]的值。我们知道，如果要实现”跳跃“k个元素，那么pattern串中i之前的k个元素要和pattern串中的前k个元素相同，即pattern[1...k]=pattern[i-k+1...i]，此时的next[i]=k。

 

由上述逻辑可得到代码如下：

/**
 *  计算next函数 
 *
 */
void computeNext(char* pattern, int* &next, int m)
{
    // 长度必须大于0 
    if(m<=0){
        return;
    }
    next[0]=-1;
    for(int i=1; i<m; i++){
        int j=next[i-1];
        while(j>=0 && pattern[j+1]!=pattern[i]){
            j=next[j];
        }
        if(pattern[j+1]==pattern[i]){
            next[i]=j+1;
        } else {
            next[i]=j;
        }
    }
}