数据结构KMP算法

D.E.Knuth, J.H.Morris 和 V.R.Pratt 共同发表模式匹配算法, 称之克鲁特-莫里斯-普拉特算法. 简称 KMP 算法.

KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)

主串S："abcababca"，模式串T："abcabx"，请找出模式串在主串中第一次出现的位置。

1.思路

BF算法是直接一个一个便利
过程:
他会根据主串S[0]和T[0]进行匹配，直到出现不相同的情况，此时会丢弃前面的匹配信息，让S[1]与T[0]相比，直到主串结束或者匹配成功，这样的方式极大的降低了匹配效率。也会增加多余的判断。

16931375-2c78f72df4438af9.png

因此，为了减少多余的判断，我们需要用一个数组next，记录模式串中匹配失败时应该回退的位置，而不是匹配失败，又从第一个数开始匹配，这样会产生多余的判断。

屏幕快照 2020-05-18 下午5.17.31.png

当 j=1时, next[1] = 0
当 j=2时, j 由 1到 j-1 范围内只有字符 “a”, 属于其他情况 next[2] = 1;
当 j=3时, j 由 1到 j-1 范围内有字符 “ab”,显然 a 不等于 b, 属于其他情况 next[3] = 1; 当 j=4时, j 由 1到 j-1 范围内有字符”abc”,显然abc 不存在相等情况,则属于其他情况 next[4] = 1;
当 j=5时, j 由 1到 j-1 范围内有字符”abcd”,显然abcd 不存在相等情况,则属于其他情况 next[5] = 1;
当 j=6时, j 由 1到 j-1 范围内有字符”abcde”,显然abcde 不存在相等情况,则属于其他情 况next[6] = 1;

当 j=1时, next[1] = 0
当 j=2时, j 由 1到 j-1 范围内只有字符 “a”, 属于其他情况 next[2] = 1;
当 j=3时, j 由 1到 j-1 范围内有字符 “ab”,显然 a 不等于 b, 属于其他情况 next[3] = 1; 当 j=4时, j 由 1到 j-1 范围内有字符”abc”,显然abc 不存在相等情况,则属于其他情况 next[4] = 1;

当 j=5时, j 由 1到 j-1 范围内有字符”abca”,显然 abca 前缀字符 “a” 与 后缀字符 “a” 相等 ; (由于 ’p1...pk-1’ = ‘ pj-k+1 ... pj-1’,得到p1 = p4) 因此可以推算出 k 值为2; 因此 next[5] = 2;
当 j=6时, j 由 1到 j-1 范围内有字符”abcab”,显然 abcab 前缀字符 “ab” 与 后缀字符 “ab” 相等; (由于 ’p1...pk-1’ = ‘ pj-k+1 ... pj-1’,得到 [p1, p3-1] = [p6-3+1,p5] ) 推导 k 值为 3, 因此next[6] = 3;

当 j=1时, next[1] = 0
当 j=2时, j 由 1到 j-1 范围内只有字符 “a”, 属于其他情况 next[2] = 1;
当 j=3时, j 由 1到 j-1 范围内有字符 “ab”,显然 a 不等于 b, 属于其他情况 next[3] = 1; 当 j=4时, j 由 1到 j-1 范围内有字符 ”aba”, 显然”aba”, 前缀字符 “a” 与 后缀字符 ”a” 相等,所以 k = 2; next[4] = 2;
当 j=5时, j 由 1到 j-1 范围内有字符 ”abab”, 显然”abab”, 前缀字符 “ab” 与 后缀字 符 ”ab” 相等,所以 k = 3; next[5] = 3;

当 j=6时, j 由 1到 j-1 范围内有字符 “ababa”,前缀 “aba” 与 后缀 “aba” 相等,那么此时 k = 4; next[6] = 4;
当 j=7时, j 由 1到 j-1 范围内有字符 “ababaa”,前缀 “a” 与 后缀 “a” 相等,那么此时 k = 2; next[7] = 2;
当 j=8时, j 由 1到 j-1 范围内有字符 “ababaaa”,前缀 “a” 与 后缀 “a” 相等,那么此时 k = 2; next[8] = 2;
当 j=9时, j 由 1到 j-1 范围内有字符 “ababaaab”,前缀 “ab” 与 后缀 “ab” 相等,那么此时 k = 3; next[9] = 3;

最后上代码

//----KMP 模式匹配算法---
//1.通过计算返回子串T的next数组;
//注意字符串T[0]中是存储的字符串长度; 真正的字符内容从T[1]开始;
void get_next(String T,int *next){
    int i,j;
    j = 1;
    i = 0;
    next[1] = 0;
    //abcdex
    //遍历T模式串, 此时T[0]为模式串T的长度;
    //printf("length = %d\n",T[0]);
    while (j < T[0]) {
        //printf("i = %d j = %d\n",i,j);
        if(i ==0 || T[i] == T[j]){
            //T[i] 表示后缀的单个字符;
            //T[j] 表示前缀的单个字符;
            ++i;
            ++j;
            next[j] = i;
            //printf("next[%d]=%d\n",j,next[j]);
        }else
        {
            //如果字符不相同,则i值回溯;
            i = next[i];
        }
    }
}

//KMP 匹配算法(1)
//返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP(String S,String T,int pos){
    
    //i 是主串当前位置的下标准,j是模式串当前位置的下标准
    int i = pos;
    int j = 1;
    
    //定义一个空的next数组;
    int next[MAXSIZE];
    
    //对T串进行分析,得到next数组;
    get_next(T, next);
    count = 0;
    //注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
    //若i小于S长度并且j小于T的长度是循环继续;
    while (i <= S[0] && j <= T[0]) {
        
        //如果两字母相等则继续,并且j++,i++
        if(j == 0 || S[i] == T[j]){
            i++;
            j++;
        }else{
            //如果不匹配时,j回退到合适的位置,i值不变;
            j = next[j];
        }
    }
    
    if (j > T[0]) {
        return i-T[0];
    }else{
        return -1;
    }
    
}

//KMP 匹配算法(2)
//求模式串T的next函数值修正值并存入nextval数组中;
void get_nextVal(String T,int *nextVal){
    int i,j;
    j = 1;
    i = 0;
    nextVal[1] = 0;
    while (j < T[0]) {
        if (i == 0 || T[i] == T[j]) {
            ++j;
            ++i;
            //如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值
            if(T[i] != T[j])
                nextVal[j] = i;
            else
            //如果当前字符与前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置
                nextVal[j] = nextVal[i];
        }else{
            i = nextVal[i];
        }
    }
}