本文共 2576 字，大约阅读时间需要 8 分钟。

字符串专题

朴素模式匹配算法

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

求模式串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] = 0for (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