09--KMP

2020-12-24  本文已影响0人  清风烈酒2157

[toc]

KMP算法原理

KMP思想

假设字符串abcdefgab和模式串abcdex,进行匹配,当匹配到x位置时,我们发现字符不相等,按照BF算法,i=1,j=1,从新开始循环,这样查找效率是很低的.

首先,假设我们知道abcde都不相等,那么i=6的时候,就没有必要再回到i=1的位置从新开始,因为a和a后面的字符都不相等,再去匹配都是多余的操作.

而, KMP算法的想法 是，设法利用这个已知信息，不要把 "搜索位置" 移回已经比较过的位置，继续把它向后移，这样就提高了效率.

e2a89c71d4a2c52a162848d1fb7e36cd

KMP 关键

没有重复字母

存在重复字母

猜想:

如果,j回溯到1的位置如果查到相同的字符,到最后匹配成功,但是这不是最优的结果,因为主串a左边ab(后缀)和主串头部ab(前缀)是重复字符串,所以只需要从模式串c开始比较.
还发现一个规律,有n个重复字符,那么开始位置就是n+1
因此得出规律: j值的多少取决于当前字符之前的串前后缀相似度;

e7fc769a9eb6b2dc133fef1b56e2fb39

其规律如图

f5c4e4b1d08571c9f7a9f1171004d603 
假如,j=6,不相等,4和5位置字符串相等,可以推出k=3 
j-k+1 = 4 ,j=6,那么k=3.

KMP匹配算法中_next 数组值推导

字符串T= 'abc'

下标 1 2 3
i a b c
j 0 1 1

假设S='bsssssss'

  1. 当 j=1,next[1]=0; //因为j=1,就匹配失败,此时 i=1,j=next[1]=0;要重新开始一轮匹配,也就是s开始和a进行比较
  2. 当 j=2,1到j-1,也就是b前面就一个a,与b不相等,所以next[2] = 1
  3. 当 j=3,1到j-1,也就是c前面字符a和b,但是都是互不相等,所以next[3] =1
下标 1 2 3 4 5 6
i a b c a b x
j 0 1 1 1 2 3

  1. 当j=4之前,都是没有重复字符,所以next[1]=0,next[2]=1,next[3] =1,next[4]=1;

  2. 当j=5,有重复字符a,通过公式推导出,k=2,也就是next[5]=2

  3. 当j=6,有重复字符'ab',通过公式推到,k=3,也就是next[6]=3.

  4. 经验所得,当前缀与后缀字符相等,k=相等字符个数n+1;

下标 1 2 3 4 5 6 7 8 9
i a b a b a a a b a
j 0 1 1 2 3 4 2 2 3
  1. j=1,next[1]=0
  2. j=2,1到j-1的字符a,next[2]=1
  3. j=3,1到j-1的字符ab,next[3]=1
  4. j=4,1到j-1的字符aba,存在前缀a和后缀a相等,next[4]= 2
  5. j=5,1到j-1的字符abab,存在前缀ab和后缀ab相等,next[5]= 3
  6. j=6,1到j-1的字符ababa,存在前缀aba和后缀aba相等,next[6]= 4,其中a是可以共用,属于重叠字符.
  7. j=7,1到j-1的字符ababaa,存在前缀a和后缀a相等,next[7]= 2
  8. j=8,1到j-1的字符ababaaa,存在前缀a和后缀a相等,next[8]= 2
  9. j=9,1到j-1的字符ababaaab,存在前缀ab和后缀ab相等,next[9]= 3
下标 1 2 3 4 5
i a a a a b
j 0 1 2 3 4
  1. j=1,,next[1]= 0
  2. j=2,1到j-1的字符a,next[2]= 1
  3. j=3,1到j-1的字符aa,存在前缀a和后缀a相等,next[3]= 2
  4. j=4,1到j-1的字符aaa,存在前缀aa和后缀aa相等,next[4]= 4
  5. j=5,1到j-1的字符aaaa,存在前缀aaa和后缀aaa相等,next[5]= 4

KMP模式匹配算法实现

计算子串T的next数组:求解next数组其实就是在求解字符串的回溯位置;
首先,子串回溯位置和主串是没有关系的.

next数组

1 2 3 4 5 6
0 1 1 1 2 3
主串 a b c a b a b c a
模式串 a b c a b x
i 0 1 2 3 4 5 6
j \ 0 1 1 1 2 3
主串 a b c a b a b c a
模式串 a b c a b x
i 0 1 2 3 4 5 6
j \ 0 1 \ \ \ \
主串 a b c a b a b c a
模式串 a b c a b x
i 0 1 2 3 4 5 6
j \ 0 1 \ \ \ \
主串 a b c a b a b c a
模式串 a b c a b x
i 0 1 2 3 4 5 6
j \ 0 1 1 \ \ \
主串 a b c a b a b c a
模式串 a b c a b x
i 0 1 2 3 4 5 6
j \ 0 1 1 \ \ \
主串 a b c a b a b c a
模式串 a b c a b x
i 0 1 2 3 4 5 6
j \ 0 1 1 1 \ \
主串 a b c a b a b c a
模式串 a b c a b x
i 0 1 2 3 4 5 6
j \ 0 1 1 1 2 \
主串 a b c a b a b c a
模式串 a b c a b x
i 0 1 2 3 4 5 6
j \ 0 1 1 1 2 3
主串 a b c a b a b c a
模式串 a b c a b x

总结

i 0 1 2 3 4 5 6
j \ 0 1 1 1 2 3

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

那么 next 数组如何应用到KMP 的查找中了?

KMP算法之next数组求解

字符数组处理过,首位放字符串长度

void getNext(String T,int* next){
    int I=0;
    int j=1;
    next[1]=0;
    while (j<T[0]) {
        if (i==0 || T[i] == T[j]){
           
            next[++j]=++I;
        }else{
            i= next[I];
        }
    }
}

KMP 查找算法

int Index_KMP(String S,String T,int pos){
    int i = pos;
    int j = 1;
    int next[MAXSIZE];
    getNext(T, next);
    while (j<=T[0] && i<=S[0]) {
        if(j==0 || S[i] == T[j]){
            I++;
            j++;
        }else{
            j = next[j];
        }
    }
    if(j>T[0]){
        return i-T[0];
    }else{
        return-1;
    }
}

打印:

 char S[MAXSIZE];
    char T[MAXSIZE];
    StrAssign(S, "abaabcabss");
    StrAssign(T, "abcab");
    int a = Index_KMP(S, T, 1);
    int next[MAXSIZE];
    getNext(T, next);
    NextPrint(next, 3);    printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",a);

```c
主串和子串在第4个字符处首次匹配（KMP算法）[返回位置为负数表示没有  匹配] 
```

KMP 模式匹配算法优化

假设主串aaaabcde,模式串aaaaax
通过kmp推出,next数组等于012345,但是当匹配到b时,需要回退第4位,但是前面字母都是重复,所以会一直不相等,知道回退到模式串a位置.
如果优化这些不必要的回退?

j 1 2 3 4 5 6 7 8 9
模式串T a b a b a a a b a
next[i] 0 1 1 2 3 4 2 2 3
nextVal[j] 0 1 0 1 0 4 2 1 0
  1. 当j=1,nextVal[1] = 0;
  2. 当j=2,b与第1个字符a不相等,nextVal[2]=1;
  3. 当j=3,a与第1个a相等,nextVal[3]=nextVal[1]=0;
  4. 当j=4,b与第2个b相等,nextVal[4]=nextVal[2]=1;
  5. 当j=5,a与第3个a相等,nextVal[5]=nextVal[1]=0;
  6. 当j=6,a与第4个b不相等,nextVal[6]=4;
  7. 当j=7,a与第2个b不相等,nextVal[7]=2;
  8. 当j=8,b与第2个b相等,nextVal[8]=nextVal[2]=1;
  9. 当j=9,a与第3个a相等,nextVal[9]=nextVal[3]=0;
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;
          
            if(T[i] != T[j])
                nextVal[j] = I;
            else
           
                nextVal[j] = nextVal[I];
        }else{
            i = nextVal[I];
        }
    }
}

分析

if(T[i] != T[j]) 这一步判断的作用,

参考

字符串匹配问题-KMP算法

上一篇 下一篇

猜你喜欢

热点阅读