09--KMP

[toc]

KMP算法原理

KMP思想

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

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

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

e2a89c71d4a2c52a162848d1fb7e36cd

KMP 关键

没有重复字母

• 如果知道i=6,我们知道6之前的字符都不相等,那么我们可以保持i=6,让j回溯到1位置,也就是f与a进行比较.
  7f8f8ef7b52fe293c2af0fee69d9d7da

存在重复字母

• 如果i=6,此时模式串应该从哪个地方开始?

猜想:

如果,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 数组值推导

• 情况1: 模式串中无任何字符重复

字符串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

• 情况2: 模式串类似于 "abcabx"

下标	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;

• 情况3: 模式串类似于 "ababaaaba"

下标	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

• 情况4: 模式串类似于 "aaaab"

下标	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数组其实就是在求解字符串的回溯位置;
首先,子串回溯位置和主串是没有关系的.

• 假设, 主串S = “abcababca” ; 模式串 T = “abcabx”
• 根据刚刚的公式的推演过程,我们其实非常情况next数组的应该是 011123 . 但是我们如何利用代码来求解出next数组了?
• 011123,意味着什么.
• 意味着其实模式串中abcabx 根本没有可以便于回溯的地址.也就是当主串与模式串不匹配时,都需要从第1的位置上重新比较;

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

• 比如 abcababca 比较 abcabx 当比较到第6个位置是发现不匹配. 而此时主串的索引不变;
• 模式串的索引j当时等于6. 而此时发现不匹配,则要进行回溯. 那么应该回溯到哪里了?
• j = next[j] ; j = 3; 也就是把abcbabca 的第6个字符与模式串的第3个字符串重新开始比较;

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

• 首先默认next[1] = 0; 表示它需要从0开始遍历;
• 接下来设计2个索引下标 i = 0, j = 1;
• i 用于求解回溯的地址, 而j用于模式串的遍历
• 如果出现i = 0,就是表示此时在模式串中并没有出现它相同的字符, 需要记录此时的回溯地址地址为1; next[j] = 1; 表示需要把从模式串的第一个字符开始比较;
• 如果T[i] == T[j] 表示此时已经出现了模式串中有重叠字符,则回溯地址next[j] = i;
• 如果既没有出现 i = 0,且 T[i] == T[j] 表示此时从[i,j]这个范围没有出现回溯位置的调整,我们则把 i 回溯到next[i] 的位置,也就是回溯扩大范围匹配;
• 这个过程我们通过图例来分析! 这是KMP算法.也是众多匹配算法中最为难以理解的算法;

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,且j = 1的情况下.也是就是我们要找到[0,1]这个范围的字符 a 是否存储需要回溯的情况.
• 而这是只有字母 a,并且当前 i = 0, 所以如果主串和模式串匹配是遇到第2个字符就不相配. 那么就应该主串后移1位,并且与模式串重新的第1位开始重新匹配计算;
• 但是此时i=0,j = 1; 所以我们应该i++,j++;
• 并且将next[j] = i; 所以此时next[2] = 1;
• 表示,当j=2时,发现字符不匹配.需要把控制模式串比较的下标索引回溯到1. 从第一个字符重新开始比较;

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 = 1,j = 2; 明白此时在[0,2]范围内,没有可以回溯的合理位置;
• 所以将i回退到next[1]. 也就是 i = next[I];
• 那么如果i = 1,next[1] = 0;也就是0的位置; 0就意味着我们需要下一个字符进行比较时,我们需要头开始比较;
• 那么如果是 next[i] 等于其他位置,表示把i回溯到其他位置. 而只有i有可回溯的可能性才会回溯到其他位置.

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. 所以i++,j++; 因为这是当j = 3时, 如果不匹配需要回溯到开始的位置. 所以j 也是要++ 的;
• 同时next[j] = i; next[3] = 1;

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 = 1, j = 3; 那么我们要看看这个范围内是否出现回溯的可能性;
• 而此时T[i] != T[j], a != c ,所以此时应该回到开始的位置;
• 也就是 i = next[i]; 此时 i 等于0 .
• 表示下一次的比较,要重头开始;

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,也就意味着.当j = 4时, 是需要从头开始比较;

• 那么 i++,j++,同时next[j] = I;

• 此时,i = 1,j = 4, next[4] = 1;

• 此时在[1,4] 范围内看有没有可以减少回溯长度的位置

• 但是T[i]=T[j], a = a, 不必从头开始;

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 = 1,也就意味着.当j = 4时, 不需要从头开始;

• 那么 i++,j++,同时next[j] = I;

• 此时,i = 2,j = 5, next[5] = 2;

• 此时在[2,5] 范围内看有没有可以减少回溯长度的位置

• 但是T[i]=T[j], b = b, 不必从头开始;

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 = 2,也就意味着.当j = 5时, 不需要从头开始;

• 那么 i++,j++,同时next[j] = I;

• 此时,i = 3,j = 6, next[6] = 3;

• 循环结束

总结

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

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

• 默认next[1] = 0;
• 当 i=0时,表示当前的比应该从头开始.则i++,j++,next[j] = i;
• 当 T[i] == T[j] 表示2个字符相等,则i++,j++.同时next[j] = I;
• 当 T[i] != T[j] 表示不相等,则需要将i 退回到合理的位置. 则 i = * * next[i];

那么 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位置.
如果优化这些不必要的回退?

• 当匹配到字母不相等时,查看模式串前面字符是否与当前字符相等的字符,如果存在,直接回到与之相等的那个字符下标对应的next数组的值.

• 现有模式串ababaaaba

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]) 这一步判断的作用,

• 当匹配到j字符不相等时,我们会拿到j下标next数组里面值进行回退,但是回退的地方字符和当前字符相等,那么nextVal[j] = nextval[next[j]],
  而,next[j]是等于i的,所以要先++j,++i,这是第++j为对应的next的数组值++i;

参考

字符串匹配问题-KMP算法