KMP算法详解

字符串专题

朴素模式匹配算法
int Index (SSTring S, SString T) {
    int k = 1;
    int i = k;
    int j = 1;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            i++;
            j++;	//字符匹配成功,继续比较后继字符
        } else {
            k++;	//匹配不成功,主串S指针回退 
            i = k;
            j = 1;
        }
    }
    if (j > T.length) {
        return k;
    } else {
        return 0;	//这种情况是主串已经判断完,但是要匹配的串还未完,所以匹配失败
    }
}
KMP算法

一、基础知识

​ 串的前缀:包含第一个字符,且不包含最后一个字符的子串

​ 串的后缀:包含最后一个字符,且不包含第一个字符的子串

​ 当第j个字符匹配失败,由前1 ~ j – 1个字符组成的串记为S,则:next[j] = S的最长相等前后缀长度+1

​ 特别的, next[1] = 0

例如:模式串:’ababaa’

  • 序号j = 1的时候,S = ‘a’

  • 序号j = 2的时候,S = ‘a’此时没有前缀和后缀所以最长相等前后缀长度为0 + 1

  • 序号j = 3的时候,S = ‘ab’ 此时前缀和后缀最长相等长度为 0 + 1

  • 序号j = 4的时候,S = ‘aba’ 前缀 = ‘a’ 后缀 = ‘a’ 2 + 1

  • 序号j = 5的时候,S = ‘abab’ 前缀 = ‘ab’ 后缀 = ‘ab’ 2 + 1

  • 序号j = 6的时候,S = ‘ababa’ 前缀 = ‘aba’ 后缀 = ‘aba’ 3 + 1

序号j 1 2 3 4 5 6
模式串 a b a b a a
next[j] 0 1 1 2 3 4
求模式串T的next数组
void get_next(SString T, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
   	while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            i++;
            j++;
            //若pi = pj , 则next[j + 1] = next[j] + 1
            next[i] = j;
        } else {
            //否则令j = next[j], 循环结束
            j = next[j];
        }
    }
    
    
}

求next数组的代码详细解释:

1619615507946

图解:

加入此时k + 1 = 17

1619615567001

已知next[16]的值,所以可以知道下图圈起来的部分重合

1619615742507

然后根据流程2,要求的是next[k + 1],假如此时P8 = P16成立

  • 假如P8 = P16 也就是说下图部分重合,所以next[k + 1] = 8 + 1 = 91619615843511

  • 假如P8 != P6

3、如果next[8] = 4,则有以下关系

1619616042747


4、现在再判断,如果P16 = P4则next[17] = 4 + 1 = 5

蓝色重合

1619616179587

1619615949355

1619678101692

然后比较p2是否等于p16

1619678154221

KPM算法
int Index_KMP (SString S, SString T) {
    int i = 1;
    int j = 1;
    int next[T.length + 1];
    get_next(T, next);	//求模式串的next数组
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            i++;
            j++;		//继续比较后继字符
        } else {
        	j = next[j];	//模式串右移
        }
        
    }
    
    if (j > T.length) {
        return i - T.length;	//匹配成功
    } else {
        return 0;
    }
}
总结

朴素模式匹配算法的缺点:当某些子串与模式串能部分匹配时,主串的扫描指针i经常回溯,导致时间开销增加。最坏时间复杂度O(nm)

KMP算法:当子串和模式串不匹配时,主串指针i不回溯,模式串指针j = next[j],算法平均时间复杂度:O(n + m)
next数组手算方法:当第j个字符匹配失败,由前1 ~ j - 1个字符组成的串记为S,则:next[j] = S的最长相等前后缀长度 + 1
特别地,next[1] = 0
KMP算法存在的问题(next数组的优化问题)

1619679047592

如上图,I与g不匹配,所以指针j会指向next[j]的位置,也就是j会指向1的位置,此时字母为g

1619679111723

观察可知,第一个字母与第一次j指向的字母相同,所以这就相当于多进行的没必要的比较。

这个时候就需要进行next数组的优化

1619679366096

也就是让4的next的值,变为next[4] = next[next[4]]

1619679478170

优化代码实现
先求出next数组
先令nextval[1] = 0
for (int j = 2; j <= T.length; j++) {
    if (T.ch[next[j]] == T.ch[j]) {
        nextval[j] = nextval[next[j]];
    } else {
        nextval[j] = next[j];
    }
}

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

d4d59d818c23770f6bce192a1a9c3240