KMP算法详解

2022-01-02 05:27:17

字符串专题

朴素模式匹配算法

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数组的代码详细解释：

图解：

加入此时k + 1 = 17

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

然后根据流程2，要求的是next[k + 1]，假如此时P₈ = P₁₆成立

假如P₈ = P₁₆ 也就是说下图部分重合，所以next[k + 1] = 8 + 1 = 9
假如P₈ != P₆

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

4、现在再判断，如果P₁₆ = P₄则next[17] = 4 + 1 = 5

蓝色重合

然后比较p₂是否等于p₁₆

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数组的优化问题)

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

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

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

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

优化代码实现

先求出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

码农公寓