菜鷄日記——KMP算法及其优化与应用

xiaoxiao2021-03-01  14

一、什么是KMP算法

KMP算法,全称Knuth-Morris-Pratt算法,由三位科学家的名字组合命名,是一种性能高效的字符串匹配算法。假设有主串S与模式串T,KMP算法可以在线性的时间内匹配出S中的T,甚至还能处理由多个模式串组成的字典的匹配问题。

二、KMP算法原理及实现

普通的匹配算法:

首先将S和T首位对齐;从前往后扫描T,与S的对应位置匹配;若发现某位不匹配则将T后移一位,然后再重复步骤2;若T完全匹配S中的某一段或T无法再后移则匹配结束。

KMP算法的核心在于,一旦遇到某个位置的字符匹配失败,则利用预处理T得到的部分匹配表对T进行“快速”的“后移”,大量减少不必要的匹配工作。所谓的“快速”,即根据T本身的结构特征一次移动至少一位以上。部分匹配表用数组next[1..T.len]表示,next[1]=0,next[i]=k(0<k<i)当且仅当T[1..k]==T[i-k+1..i]且不存在k<k'<i使得T[1..k']==T[i-k'+1..i],即next[i]表示T[1..i]前缀和后缀最大的匹配。

next[1..T.len]的求解过程:

next[1]=0; i>1时,假设next[i-1]已经求得,令k'=next[i-1];由上述定义可知前缀T[1..k']和后缀T[i-k'..i-1]匹配;若T[k'+1]==T[i],则T[1..i]的前缀T[1..k'+1]和后缀T[i-k'..i]匹配,可得next[i]=k'+1;否则令k''=next[k'],可知T[1..k'']和T[1..k']、T[1..i-1]有长度为k''的公共后缀,令k'=k'';重复步骤3、4、5直到k'==0但T[1]!=T[i],此时next[i]=0。 void GetNext() { nxt[1] = 0; // C++11 中 next 是标准库中的函数名,所以此处用 nxt int k = 0; for (int i = 2; i <= T.len; i++) { while (k > 0 && T[k + 1] != T[i]) k = nxt[k]; //k + 1 < i 恒成立 nxt[i] = (T[k + 1] == T[i]) ? ++k : 0; } }

假设S为abcbaabcbcacbabcacabacb,T为abcbaabccab(下标皆从1开始)。

        abcbaabcbcacbabcacabacb        abcbaabcbcacbabcacabacb

        abcbaabccab                                           abcbaabccab

普通的匹配算法,对于上例从左边的状态到右边的状态要对T进行5次右移的操作,并且每一次移动后都要重新从左到右每位匹配。但是KMP算法只需要对上例的T右移1次即可到达右边的状态,并且不需要再从头开始扫描。可以得到T(abcbaabccab)的部分匹配表为next[1..11]={0,0,0,0,1,1,2,3,0,1,2}。假设作用于S和T的下标标记分别为i和j,则左边i=j=8,显然左边S[i+1]!=T[j+1](b!=c)。因为next[8]=3,根据上面所说即有T[1..3]==T[6..8],所以令j=next[j]=3就相当于一次性将T右移8-3=5个位置得到右边,此时S[i+1]==T[j+1]则令i++、j++,否则继续令j=next[j]。

KMP算法的匹配过程:

令作用于T的下标标记j=0,从左至右扫描S;对于S[i],若T[j+1]!=S[i]则令j=next[j]直到T[j+1]==S[i]或j==0;若T[j+1]==S[i]则++j;若步骤3执行后j==T.len则表示T能匹配S中的某一段;若S扫描完毕却没能找到匹配则匹配失败。 bool KmpMatch() { int j = 0; for (int i = 0; i < S.length(); i++) { while (j > 0 && j < T.len && T[j + 1] != S[i]) j = nxt[j]; if (j < T.len && T[j + 1] == S[i]) ++j; if (j == T.len) return true; } return false; }

KMP算法求取部分匹配表的时间复杂度为O(|T|),匹配过程的时间复杂度为O(|S|),所以总的时间复杂度为O(|S|+|T|),相比于普通匹配算法的O(|S|*|T|)来看性能高效。

三、KMP算法的优化

例如T为aaaaaaa,则其部分匹配表为next[1..7]={0,1,2,3,4,5,6},当T与S匹配过程中一直到T的最后一个a(此时j=6)发生不匹配,按照上述的KMP算法的匹配过程,需要令j=next[j]直到T[j+1]==S[i]或j==0,因此语句j=next[j]需要执行6次。通过观察发现,假设next[j]=k则有T[1..k]==T[j-k+1..j],若T[k+1]==T[j+1]则当T[j+1]!=S[i]时令j=next[j]仍是意义不大,但是若T[k+1]!=T[j+1]则通过令j=next[j]可能使得T[k+1]==S[i],因此可以通过优化部分匹配表减少无意义的“右移”。用nextval[1..T.len]数组表示优化后的部分匹配表,上述的部分匹配表构造过程,将“next[i]=k'+1”替换为“当T[k'+2]==T[i+1]时nextval[i]=nextval[k'+1]否则nextval[i]=k'+1”(需要注意的是:因为nextval[k'+1]已经在nextval[i]前求得,所以只要令nextval[i]=nextval[k'+1]就已经能保证T[nextval[k'+1]+1]!=T[k'+2]==T[i+1]而不需要往前扫描)。

void GetNextval() { nextval[1] = 0; int k = 0; for (int i = 2; i <= T.len; i++) { while (k > 0 && T[k + 1] != T[i]) k = nextval[k]; //k < i <= T.len 恒成立 if (T[k + 1] == T[i]) nextval[i] = (i < T.len && T[k + 2] == T[i + 1]) ? nextval[++k] : ++k; else nextval[i] = 0; } }  a a a a a a a a b c a a b b a b c a bnext0 1 2 3 4 5 6 0 0 0 1 1 2 0 1 2 3 4 2nextval0 0 0 0 0 0 6 0 0 0 1 0 2 0 0 0 0 4 2

可见对于上例,优化后的部分匹配表可以只执行1次j=nextval[j]就完成了未优化前的6次“右移”。

四、KMP算法的应用

1、字符串匹配

判断模式串是否在主串中出现、出现的次数、出现的位置;判断字典中的单次在文本中是否出现、出现的次数、出现的位置。上述代码只能判断模式串是否在主串中出现,如果需要知道模式串出现的次数以及出现的位置,在匹配的过程引入一个用tend[0..S.len-1]的匹配表,tend[i]=k(0<=k<=min(T.len,i))当且仅当T[1..k]==S[i-k+1..i]且不存在k<k'<=min(T.len,i)使得T[1..k']==S[i-k'+1..i],即tend[i]表示T的前缀与S[0..i]的后缀的最大匹配,当tend[x]=T.len时表明T在S中成功匹配1次且i-T.len+1即为匹配的位置。由于tend[]数组和next[]数组的定义类似,都是关于前缀和后缀的最大匹配问题,因此可以类比next[]数组的求解方法得到tend[]数组。

void KmpMatch() { int j = 0; for (int i = 0; i < S.length(); i++) { while (j > 0 && j < T.len && T[j + 1] != S[i]) j = nxt[j]; if (j < T.len && T[j + 1] == S[i]) ++j; tend[i] = j; } for (int i = 0; i < S.length(); i++) if (tend[i] == T.len) pos[cnt++] = i - T.len + 1; }

对于字典的情况,给每个词条都分别生成部分匹配表并与文本匹配即可。

2、字符串循环节的判断

根据优化之前的部分匹配表next[]的特征可以判断T是否由循环节构成,得到最小循环节长度和最小循环节。令m=T.len、k=next[m],ΔL=m-k,因为T[1..k]为T[1..m]的后缀,所以任意1<=i<=k都有T[i]==T[i+ΔL]。根据等价关系“任意i<j,T[i]等价于T[j]当且仅当ΔL整除j-i“,T可以分成分成ΔL个等价类,代表元分别为T[m-ΔL+1]、T[m-ΔL+2]、…、T[m]。当ΔL|m(ΔL整除m)时,T由循环节构成,最小循环节长度为ΔL,有m/ΔL个最小循环节,最小循环节为T[T.len-ΔL+1..T.len]。

转载请注明原文地址: https://www.6miu.com/read-4050314.html

最新回复(0)