数据结构与算法14-字符串匹配与KMP

2020-05-06  本文已影响0人  fuaiyi

什么是KMP

KMP算法是在字符串匹配算法中比较绕的.主要是需要理解KMP中next数组求解的必要性以及j 的回溯依据; 在理解KMP 算法时, 很容易头秃. 这个算法可以多理解几次, 理解的过程中更加透彻;
KMP 算法也是比较著名的模式匹配算法. 是由D.E.Knuth,J.H.Morrs 和VR.Pratt. 发表的一个模式匹配算法. 可以大大避免重复遍历的情况;

KMP 模式匹配算法原理

case1:

例如,假设现在有一个主串S = “a a acaaab” ; 模式串 T = “aaab” ; 如果使用暴风算法的话,前面5个字母完全相等,直到第6个字母.'f' 和 'x' 不相等; 如下图;


image.png

接下来按照爆发算法,我们需要执行的过程.即主串i=2,3,4,5,6时,首字母与子串T的首字母均不相等;


image.png

按照爆发算法的设计,我们的执行过程就是如此. 但是对于要匹配的子串T来说,"abcdex" 首字母"a" 与后面的串"bcdex"中任意一个字符都不相等;
也就是说, 既然"a"不与自己后面的子串中任何一个字符相等. 那么对于上图中①来说,前面5个字符分别相等.那就意味着子串T与首字符"a"不可能与S 串的第2位到第5位想的.
KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率

理解KMP 关键
image.png image.png
case2:

例如,假设现在有一个主串S = “abcababca” ; 模式串 T = “abcdex” ;

image.png image.png image.png image.png
case3:字符串中重复的字符比较多，该算法就显得很蠢。

比如 txt = "aaacaaab" pat = "aaab"：
暴风算法


image.png

KMP算法


image.png image.png
KMP匹配算法中_next 数组值推导
情况1: 模式串中无任何字符重复
image.png
情况2: 模式串类似于 "abcabx"
image.png 
next数组是比较连续的前缀字符和后缀字符; 例如当j=6时,字符串"ababa", 最大前缀是"aba",后缀也是"aba".
当 j = 7时,字符串"ababaa",此时前缀是"a",后缀是"a". 不要误以为是"ab";
情况3: 模式串类似于 "aaaaaaaab"
image.png

重叠的情况下，前缀和后缀可以共用
计算子串T的next数组:求解next数组其实就是在求解字符串的回溯位置;
KMP next数组的回溯位置求解过程模拟

image.png image.png

1⃣️ 默认next[1] = 0
2⃣️ i= 0，j=1开始遍历
3⃣️ 当j<s.length j从1～length遍历字符串
4⃣️ 如果当i = 0 表示[ i , j ] 这个范围内没有找到相同的字符，所以i要回溯到1的位置；表示next[j] = 1
5⃣️ 如果当T[i] = T[j] 相等，表示找到了相等的字符的位置吗所以next[j] = i ;
6⃣️ 当以上两个条件都不成立的时候，则将i回溯到前面记录的位置的next[i]的位置

image.png image.png image.png image.png

在求解next数组的4种情况:

  1. 默认next[1] = 0;
  2. 当 i=0时,表示当前的比应该从头开始.则i++,j++,next[j] = i;
  3. 当 T[i] == T[j] 表示2个字符相等,则i++,j++.同时next[j] = i;
  4. 当 T[i] != T[j] 表示不相等,则需要将i 退回到合理的位置. 则 i = next[i];
    那么 next 数组如何应用到KMP 的查找中了?
image.png
KMP算法之next数组求解
//----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查找算法
int count = 0;
//KMP 匹配算法
//返回子串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 0;
    }
}
KMP匹配算法优化

KMP 算法也是有缺陷的. 比如,如果我们的主串S="aaaabcde",模式串T="aaaaax",其中 next 数组就是 012345

image.png

其实,在比较的过程发现 当中②③④⑤步骤的回溯比较都是多余的判断;
由于 T 串的第二,三,四,五位置的字符都与首位 "a" 相等, 那么可以用 首位 next[1] 的值去取代与它相等的字符后续的 next[j] 值. 那么我们来对 next 函数来进行改良;
next 数组= {0,1,2,3,4,5}
如果要节省刚刚 ②③④⑤ 的无效比较则 需要next 数组={0,0,0,0,0,5}

KMP 模式匹配next 数组的优化
image.png image.png image.png image.png image.png
KMP_NextVal 数组逻辑

在求解nextVal数组的5种情况:

  1. 默认nextval[1] = 0;
  2. T[i] == T[j] 且++i,++j 后 T[i] 依旧等于 T[j] 则 nextval[i] = nextval[j]
  3. i = 0, 表示从头开始i++,j++后,且T[i] != T[j] 则nextVal = j;
  4. T[i] == T[j] 且++i,++j 后 T[i] != T[j] ,则nextVal = j;
  5. 当 T[i] != T[j] 表示不相等,则需要将i 退回到合理的位置. 则 i = next[i];
代码实现KMP_NextVal数组
void get_nextVal(String T,int *nextVal){
    int i,j;
    i = 1;
    j = 0;
    nextVal[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++j;
            ++i;
            //如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值
            if(T[i] != T[j])
                nextVal[i] = j;
            else
            //如果当前字符与前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置
                nextVal[i] = nextVal[j];
        }else{
            j = nextVal[j];
        }
    }
}

视屏讲解

上一篇 下一篇

猜你喜欢

热点阅读