字符串的KMP算法

点击打开在线编译器,边学边练

1. 原由

紧接上文,我们知道了暴力匹配的算法在时间运行上的缺陷,假设字符串T的长度为n,字符串P的长度为m,则整个算法的时间复杂度为O( n * m ),而对于一个复杂的现实情况而言 n >> m >> 2 (即n远远大于m,m远远大于常数),这样的计算计算机的负担很重。

请思考一个暴力匹配的情况:

给定一个主字符串

T = “AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB”(47位)

同时给定模式串 P = “AAAAAB”(6位)

试问搜索的情况,很显然,暴力搜索对于每一次搜索,都要搜索到最后一个字符才能进行下一轮的搜索,因此进行的计算近似可以理解为:O(47 * 6) ,对于这样很少的数据已经有很高的计算量了。

 

KMP算法一种改进的模式匹配算法,是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表,KMP算法又称克努特-莫里斯-普拉特操作, KMP算法与前文的暴力匹配算法,核心的区别就是没有不匹配的回溯,而是根据整个字符串的情况进行一次位移,这样大大减少了回溯产生的缺陷,KMP算法的时间复杂度可以优化到 O( n + m)级别,是二次优化到线性的程度。

 

2.构造next表(以-1开头)

对于模式串P而言,我们需要知道模式串中P的每一位的前一位是否存在相等的完全相等的前后缀,并且求这个最大的完全相等的前后缀,如一个模式串”ABCABDE”对于第倒数第二位字符而言,其符合情况的前后缀就是”AB”,而最后一位则没有完全相等的前后缀。

PS:何为前后缀:如一个字符串”ABCD”,其前缀有可能为”A”“AB”“ABC”(即除去本身的全部字符),同理,则后缀可能为:”D””CD””BCD”

我们需要求的就是每一个字符其相对应的最大前后缀数,这样与模式串P一一对应的表称之为next表。

因此”ABCABDE”的next表为:-1 0 0 0 1 2 0 (字符用空格隔开)


ABCABDE
-1000120

   


那么我们该如何实现代码呢?

对于每一个当前需要判断的字符而言,在构造next表时,应该向前进行比对,以上一个已经判断的情况为基础(初始值赋-1,部分教程中初始值赋0,两者没有实质区别),后缀如果+1位置的字符与前缀+1位置的字符相等,则next[i]就是next[i-1]+1,而如果不相等,则说明无法匹配,则next[i]=0。

 

3. KMP实现

与暴力匹配极其相似,利用while循环的条件控制, 进行匹配失败时,只需要将失败的模式串P的索引指向next表中对应的数值即可,其余匹配照旧线性执行即可。

 

4. 实现代码(仅作参考)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
int *buildNext(char *P){
    int m = strlen(P) , j=0;
    int * N = new int[m];
    int t = N[0] = -1;
    while( j < m-1 ){
        if( 0 > t || P[j] == P[t] ){
            N[++j] = ++t;
        }
        else{
            t = N[t];
        }
    }
    return N;
}
 
int KMP(char T[],char P[]){ //T--主串,P--模式串
    int *next = buildNext(P);   //构造NEXT表
    int n = strlen(T) , i=0;
    int m = strlen(P) , j=0;
    while( j<m && i<n ){
        if( j<0 || T[i]==P[j] ){
            i++;
            j++;
        }else{
            j = next[j];
        }
        
    }
    delete []next;
    return i-j;
}
 
int main(){
 
    char org[] = "ABABABABABD";
    char str[] = "ABABD";
    int ans = KMP(org,str);
    cout << ans <<endl;
 
    return 0;
}

输出6,即经过6位,在第七位发生匹配



本文固定URL:https://www.dotcpp.com/course/126

第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记
Dotcpp在线编译      (登录可减少运行等待时间)