标签（空格分隔）： 数据结构与算法

KMP算法是一个经典的字符串匹配算法,但是原理比较晦涩难懂,这里推荐一篇个人感觉分析比较好的文章,个人感觉图灵社区的这篇KMP算法解析讲解的非常的好.

对于一般的字符串匹配算法,我们一般能够想到匹配算法是暴力匹配的方式.

对于目标串S = helloworld, 匹配串T = helle,我们做如下匹配操作,我们用i,j分别表示目标串和匹配串的下标变量,i = 0 ,j = 0
首先,我们用T[0]与S字符串一位一位的比较,当出现T[0] == S[i]时,继续比较T[0+1] == S[i+1],一次进行下去,直到T串全部匹配完成或者出现不匹配.如果中途出现不匹配,就表示我们需要重新匹配,T[0]要与S[i = i+1]开始比较,重复上面的过程.

我们用图来,更清楚的说明一下这个过程:

image.png

对于这个例子,我们很高兴,同时也很遗憾,高兴的是S串的第一个字母就与T串的第一个字母成功匹配,遗憾的是,匹配到最后,却出现了不匹配的情况.红色表示出现不匹配的地方,然后该怎么做呢?

image.png

当整个过程全部执行完毕时,我们肯定可以找到我们想要的答案.

但是这个算法很慢,浪费了很多时间,我们分析一下图一,目标串和匹配串匹配了一部分,然后出现了不匹配的情况,这就表示,目标串在匹配的地方开始起就与匹配串出现了一定程度的相似度,假设前k个字符是成功匹配的,T[k+1] != S[i+k+1](i是S串匹配开始的位置即S[i] == T[0] ),也就是说S[i..i+k] == T[0..k],即T串的某种关系S串也是适用的.

我们分析一下T串,我们发现T串中所有的字符串都不一样:
结合上面的关系:

S[i..i+k] == T[0..k]
T串每一个字符都不一样,T[0] != T1] != T[2]....!=T[N]

这其实就告诉我我们一个信息,当我们出现不配的时候,我的T[0]还有必要从S[i+1]位置开始比较吗?
显然,我们不需要,因为S[i+1] == T[1] != T[0],那么不从S[i+1]处又应该重何处呢,答案也很明显S[i+k+1]处(即上次产生不匹配的位置),因为前k个元素,我们是已知的不可能和T[0]出现匹配的.

image.png

这样我们就可以省去很多不必要的比较运算,从而加快算法的运行.

那么有人就说了,你这个T串很特殊啊,每一位都不相等,这样并不通用啊.是的,单这样给了我们一个启发,我们能不能通过利用匹配串T自身的某种关系,从而加快匹配的运算呢?
说白了,就是出现不匹配时,我们的T串应该回溯的S串的哪一个位置,进行重新匹配比较.

下面就出现了我们的主角KMP算法:减少匹配冗余步数的精髓在于对匹配串T进行预处理,把预处理的结果,保存在一个数组中,这个数组中的值,就是当出现不匹配时,T串应该回溯的位置,因此我们将这个数组称为Next数组.

KMP算法原理

核心就是一句话:寻找最长首尾匹配位置

什么意思呢?就是我们需要一个函数Next(char* N),这个函数的功能如下:
对于任意给定一个字符串N(长度为n),找出是否存在这样的i使得N[0]==N[n-i],N[0+1]==N[n-i+1],...,N[i]==N[n],如果存在则返回i的值,否则返回-1.并且不会找出一点k，k>i且满足N[0]==N[n-k]，N[0+1]==N[n-k-1]，……，N[k]==N[n].也就是说i是所有满足条件中的最大的.

image.png

上面的理论不难理解,就是任意给定一个字符串str找出这样符合条件的i.找个i有什么用呢?

我们继续看下面一个图:我们有目标串S和匹配串T,满足如下图所示的条件:T[n+1]位出现不匹配.

image.png

image.png

我们可以想象一下,不断的移动T串和S串进行匹配,只有当挪动到上图的位置时,才开始出现可能匹配的情况,yejiushiu也就是说,我们只需要比较T[i+1]位置和S串上次匹配失败的位置(途中的红色位置)比较就行了,这里就是下一次匹配最可能出现的起始位置.

这样的操作就大大减少了我们不必要的回溯比较,从而加快了字符串的比较.
也就是说,当我们在T[n+1]位置出现不匹配时,我们只需要回溯到i就行了,比较i+1位置值.然后,代码依次进行下一轮比较.

也就是说,我们的任务是,当T串在N+1位置出现不匹配时,我们只需要找到符合T[0..N]字符串条件的i就可以加快下一次匹配的进行,事实上,我们并不能确定到不匹配的位置会出现在什么位置,因此,我们需要做好每一个都有可能出现不匹配的情况,也就是说,我们需要准备一个数组,去存放这样的回溯值,对应着当T[i]出现不匹配时,我们需要回溯到pos = Next[i]位置.

下面我们就来求解这样的数组.

1. next原理递归实现

我们先上代码,然后解释:这里的我用的是java代码实现的

/**
 * 查找从j+1长度的字符串的最大首尾匹配位置
 * j=0,表示的字符串只有一个字符,没有首尾,表示的直接表示不匹配,我们用-1表示,
 * 返回的值实际上是最大匹配字符串的字符下标
 * 例如aa则返回的是0,表示的是这个字符串index=0的位置是最大匹配位置
 * @param N
 * @param j
 * @return
 */
public static int next(char[] T,int j){
    if(j == 0 )
        return -1;
    
    //如果第j-1位的首尾匹配已经知道是i
    int i = next(T,j-1);
    
    //第一种情况：i+1位和 j-1 +1位是否相等
    if(T[i+1]==T[j])
        
        return i+1;//相等则收尾匹配长度位数加1
    
    else{ //不等
        
        //不断的向前搜索最大相同字符串,然后看看加1的位置是否与之匹配,如果匹配在得到最大匹配长度
        //这里如果不懂,可以看下图
        while(T[i+1] != T[j] && i>=0){
            i = next(T,i);
        }
        //循环完成之后,肯定会出现两种情况
        //1.T[i+1] == T[j] 这种情况我们返回结果
        //2.i == -1 ;我们巧妙的利用-1+1 = 0 来表示 没有一个位置匹配出现的+1位置是0号位,这样也不会出现数组越界情况
        if(T[i+1] == T[j]){ 
            return i+1;
        }else {
            return -1;
        }
    }
}

上面的代码是递归实现:next函数返回的是长度为j+1,j表示最后一个字母的下标,的字符串最长首尾匹配位置i

KMP.png

1. 如果字符只有一个字母,我们定义为-1表示,没有匹配的位置.一个字母没有首尾可言.
2. 当j>0时,我们认为它前j-1个字符组成的字符串已经算好了i的值,我们只是在其基础上增加一个字母,如果T[i+1]=T[j],则表示next[j] = next[j-1]+1
3. 如果不相等呢?
   我们该怎么办呢?难道我们需要两端同时从后向前搜索进行暴力比较吗? 我们看上图,y和x不等,
   我们发下A1和A2部分是完全对称的,我们思考一下,若存在一端收尾对称的部分,例如T[C1+x = C4+x这样我们就找到了,对于C1和C4是否会存在一定的关系呢?
   我们看上图A1 = A2 我们对求解next[A1]可以得出B1和B2的关系,同样在A2中会对应着出现B3和B4的关系,我们最有可能出现匹配的最大值就是T[B1+1]与T[j]进行比较,因为B1是最大收尾对应的部分,依次类推,我们可以确定,C1肯定是对某一段子串的next值.于是,我们只要不断进行递归查询就next然后对比就可以找到最终的next[j]的值.

Next数组求解循环实现

循环的实现和递归的原理一样,这里我们就啰嗦了,直接上代码,这里我使用的是C++来实现的

/*
    获取next数组
    @param T 模式字符串
    @param len 模式字符串长度,同时也是next数组的长度
    @param next 求解的存放的next数组,
                这里应该由外部分配内存创建出来,数组的长度和T串的长度相等
*/
void getNext(const char *T, int len, int *next) {
    int i;
    next[0] = i = -1;
    for (int j = 1; j < len; j++) {
        while (i >= 0 && next[i+1] != next[j]) {
            i = next[i];
        }
        if (next[i + 1] == next[j]) {
            i++;
        }
        next[j] = i;
    }
}

匹配代码实现

/**
     * 为什么 i要从-1开始，
     * i表示的是如果j位置发生适配,
     * 那么j下一次比较应该和T[i+1]的位置比较,这样就从总体上实现了统一
     * 同时next数组中存放的没有匹配项值是-1因此，表示的如果没有匹配项应该和0位置进行比较。
     * @param S
     * @param T
     */
vector<int> matchStr(const char* S, const char* T) {
    
    int sLen = strlen(S);
    int tLen = strlen(T);
    
    vector<int> result;

    //获取next数组
    int *next = new int[tLen];
    getNext(T, tLen, next);
    
    for (int j = 0 , i = -1 ; j< sLen; j++) {

        while (i >= 0 && S[j] != T[i+1]) {
            i = next[i];
        }
        if (S[j] == T[i + 1]) {
            i++;
        }

        //查找到了一次成功的匹配
        if (i == tLen - 1) {
            result.push_back(j - i);
            //回溯复位
            i = -1;
        }
    }
    delete[] next;

    return result;
}

测试代码

int main() {
    char *source = "asbcdabcdefg";
    char *target = "bcd";
    
    vector<int> result = matchStr(source, target);
    vector<int>::iterator it = result.begin();
    while (it != result.end()) {
        cout << *it << endl;
        it++;
    }

    system("pause");
    return 0;
}